你有 n 个机器人,给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ,两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间,花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。
运行 k 个机器人 总开销 是 max(chargeTimes) + k * sum(runningCosts) ,其中 max(chargeTimes) 是这 k 个机器人中最大充电时间,sum(runningCosts) 是这 k 个机器人的运行时间之和。
请你返回在 不超过 budget 的前提下,你 最多 可以 连续 运行的机器人数目为多少。
示例 1:
输入:chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
输出:3
解释:
可以在 budget 以内运行所有单个机器人或者连续运行 2 个机器人。
选择前 3 个机器人,可以得到答案最大值 3 。总开销是 max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 ,小于 25 。
可以看出无法在 budget 以内连续运行超过 3 个机器人,所以我们返回 3 。
示例 2:
输入:chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
输出:0
解释:即使运行任何一个单个机器人,还是会超出 budget,所以我们返回 0 。
提示:
chargeTimes.length == runningCosts.length == n
1 <= n <= 5 * 104
1 <= chargeTimes[i], runningCosts[i] <= 105
1 <= budget <= 1015
解题思路:
1.双重循环分别从当前的位置开始计算,遇到满足条件的则结果+1
当然这种解法是无法通过leetcode所有案例的,依然避免不了会超时
滑动窗口:
使用双指针 left 和 right 来维护一个滑动窗口。
每次向右移动右指针 right,并将对应的充电时间和运行成本加入到总和中。
维护当前窗口内的最大充电时间 maxChargeTime。
检查当前窗口内的总充电时间和总运行成本是否满足预算条件。
如果不满足条件,则向右移动左指针 left,并从总和中减去对应的充电时间和运行成本。
更新最多可以购买的机器人数量。
标签:chargeTimes,runningCosts,机器人,budget,运行,预算内,充电,2398
From: https://www.cnblogs.com/java-cheng/p/18412662