LC9-13

2398. 预算内的最多机器人数目

你有 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

本道题目可以归为求最优子数组否和某个条件，对于这一类题目都可以使用双指针(滑动窗口)来解决。每次滑动都进行条件判断，如果符合，就进行答案更新。这里面有个判断是需要求滑动窗口的最大值的条件，可以使用平衡树解决,如Java中的TreeMap,因为有重复值，所有用TreeMap,如果没有重复值的话可以使用TreeSet,更优的解法就是使用单调队列，LC上有道固定窗口的原题。

class Solution {
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        int ans = 0, n = chargeTimes.length;
        TreeMap<Integer, Integer> map = new TreeMap<>(Comparator.comparing(e -> -e));
        long s = 0;
        for (int r = 0, l = 0; r < n; r++) {
            map.merge(chargeTimes[r], 1, Integer::sum);
            s += runningCosts[r];
            while (l < n && l <= r && (long) s * (r - l + 1) + map.firstKey() > budget) {
                int v = chargeTimes[l];
                map.merge(v, -1, Integer::sum);
                if (map.get(v) == 0) map.remove(v);
                s -= runningCosts[l++];
            }

            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

// 单调队列解法，单调队列一般适用于求某区间的单调最值
func maximumRobots(chargeTimes []int, runningCosts []int, budget int64) int {
    var q []int
    s := int64(0)
    l, n, ans := 0, len(chargeTimes), 0
    for r := 0; r < n; r++ {
        for len(q) > 0 && chargeTimes[q[len(q)-1]] <= chargeTimes[r] {
            q = q[:len(q)-1]
        }
        q = append(q, r)
        s += int64(runningCosts[r])
        for len(q) > 0 && int64(chargeTimes[q[0]]) + int64((r-l+1))*s > budget {
            if q[0] == l {
                q = q[1:]
            }
            s -= int64(runningCosts[l])
            l++
        }
        ans = max(ans, r-l+1)

    }
    return ans
}