预算内的最多机器人数目——二分答案和单调队列

发表于 更新于 分类于 阅读次数： 本文字数： 3.8k 阅读时长 ≈ 7 分钟

题目描述

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
2
3
4
5
6
7
8
输入：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 。

解题思路

这题的关键是连续。

因为连续，我们可以得出这样一个结论：

假设说有k为最多的可以连续运行机器人数目，那么必定有 k-1，k-2，k-3 ... 的机器人满足条件。

反过来，那就必定有 k+1，k+2，k+3 ... 的机器人不满足条件。

而且k的范围必定在 [0, chargeTimes.size()] 里

这样想，其实我们可以使用二分查找，来查找我们的答案。因为对于k的范围而言，k的范围可以视为一个单调递增的数组。而k相当于二分查找中的mid，mid左边的数满足条件，mid右边的数不满足条件。

为了方便，我们使用开区间写法（不用考虑mid+1）

1
2
3
4
5
6
7
int left = 0, right = chargeTimes.size()+1;
while (left + 1 < right) {
    int mid = (left + right) / 2;
    if (check(mid)) left = mid; 
    else right = mid;
} 
return left;

这个时候 left 就是答案。

这里的check函数的作用是，检测k个连续的机器人是否合法，合法的标准是 max(chargeTimes) + k * sum(runningCosts)。转换一下，其实可以翻译成，在一个数组中，取n个长度为k的滑动窗口，判断这n个窗口中，是否存在一个窗口满足条件。

这样看，是不是和239. 滑动窗口最大值 的思路十分相似。

接下来，我们先来解决这个题目。

前置题目和单调队列

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

对于这道题而言，暴力解法就是取长度为k的滑动窗口，遍历整个数组，依次取窗口的最大值，最后返回结果即可。假设每个窗口大小为1的情况下，暴力解法的时间复杂度为O(n^2)，会明显地超时。

另一种想法是，每次的滑动窗口的最大值，并不需要我们每次重新求值，而是可能和上次的值有关。

例如，[1,3,-1,-3,5,3,6,7]

1
2
3
4
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3

第一个窗口和第二个窗口的最大值其实是重复的，因为第二个滑动窗口向右滑动的时候，新加入的-3并没有大过3，而且，左边的边界收缩的时候，3也并没有移除，所以取3。

既然如此，我们只要维护每个窗口的最大值就行了？

最直白的想法，可能是使用优先队列priority_queue， 但是对于优先队列，找到最大值很容易，移除元素很困难，因为我们要维护最大值。

如果有一种队列能够保持最大值且删除元素很容易，那就好了

抱着这样的想法，我们可以引入单调队列。

push时，每次都保证队头元素为最大的元素。

1
2
3
4
5
6

void push(int val) {
    while (!q.empty() && q.back() < val) q.pop_back();
    q.push_back(val);
}

pop时，当队头元素为目标元素时，应该将其移除。

1
2
3
4
5

void pop(int val) {
    if (!q.empty() && q.front() == val) q.pop_front();
}

这样，我们再使用滑动窗口的思想，当窗口长度为k时，取队头元素，使用pop(val)移除元素，不为k时，则维护最大值，使用push(val)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    deque<int> que;
    void pop(int val) {
        if (!this->que.empty() && this->que.front() == val) this->que.pop_front();
    }
    void push(int val) {
        while (!this->que.empty() && this->que.back() < val) this->que.pop_back(); // 比最大值小的数且在最大值前面的数无意义 可以直接去掉
        this->que.push_back(val);
    }
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int left = 0;
        vector<int> ret;
        for (int right = 0; right < nums.size(); ++right) {
            int len = right - left + 1;
            this->push(nums[right]);
            if (left <= nums.size() - k && len == k) {
                ret.push_back(this->que.front());
                this->pop(nums[left++]);
            }
        }
        return ret;
    }
};

解决本题

对于本题的max(chargeTimes) + k * sum(runningCosts)合法条件，max(chargeTimes)其实就是维护每个长度为k的滑动窗口的最大值，对于sum(runningCosts)，维护的是每一个窗口的总和。

这样一来，思路就很明显了。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
public:
    deque<int> q;
    void push(int val) {
        while (!q.empty() && q.back() < val) q.pop_back();
        q.push_back(val);
    }
    void pop(int val) {
        if (!q.empty() && q.front() == val) q.pop_front();
    }
    int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
        function<bool(int)>check = [&](int k) {
            q.clear(); // 每次判断前 一定要进行初始化 否则会导致上一次的最大值残留
            // 求取每个窗口的最大值
            int l = 0, n = chargeTimes.size();
            long long sum = 0;
            for (int r = 0; r < n; ++r) {
                int len = r - l + 1;
                this->push(chargeTimes[r]);
                sum += runningCosts[r];
                if (l <= n - k && len == k) {
                    if ((q.front()+k*sum)<= budget) return true;
                    this->pop(chargeTimes[l]);
                    sum -= runningCosts[l++];
                }
            }
            return false;
        };
        int left = 0, right = chargeTimes.size()+1;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if (check(mid)) left = mid;
            else right = mid;
        } 
        return left;
    }
};

时间、空间复杂度分析

以下n为chargeTimes数组的长度

时间：O((log 2)*n) 二分答案加滑动窗口
空间复杂度： O(n) 假如k为n时，需要申请大小为n的双端队列。