当前位置：首页 > article >正文

LEETCODE 每日一题（单调栈 +滑动窗口模拟）

article 2024/11/14 12:35:56

下面是题目的具体描述：
你有 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 。

然后是问题的简单分析：
1.首先这个题目的关键是抓住关键字连续的子序列，所以这个题目我们大概率会使用类似滑动窗口这样的思路，而且这个题目还存在最大值这样的字样，其实（我最开始没想到，好久没做单调栈了，所以记录一下，菜还是要多练）结合这个题目的思路是要用到单调栈的（至于原因我们下面详细分析一下）。

2.其实针对这个题目我们第一时间最直观的想法就是固定左端点l，然后枚举r，如果r超过我们的目标预算budget的话，我们就l++，这个思路其实是没问题的，但是我最开始卡在这个如何保存最大值的问题上面，也就是我们把这个l++之后如何确保我们的当前的max，是否会发生变化，因为其实sum很好变化，只需要减去chargeTimes[l]即可了，卡在这好久，然后借鉴了别人的思路发现用了单调栈（哎，恍然大悟啊），其实对于我们来说是这样的我们只需要维持一个单调递减的单调栈，然后每次如果需要超过预算之后我们需要去掉最左侧的元素的话，那么我们就可以直接去判断这个去掉的元素和栈顶最大元素是否相等，如果不相等就直接l++即可，否则栈顶元素pop即可，这样就可以去维持我们每次计算时候的最大值了，（这个其实就是单调栈这个结构存在的问题背景意义，还是理解的不够深刻）下面举一个例子来简单看一下这个过程：
示例1：
chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
就用这个来看一下单调栈去模拟这个最大值的过程：
1.对于第一次是3入栈 3 + 2 * 1 = 5 < budget 所以合法，而且栈内最大元素为3

2.对于第二次是6入栈,这个时候我们就要更新了，因为我们要维持栈内是一个递减序列，前面我们的3是比6小的，那么他也就没有存在的意义了（后面的序列包含3就一定会包含6，最大不可能为3），也就是我们需要把栈内比6小的都弹出去，这时候计算一下预算 6 + 2 * （1 + 2） = 12 < 25

3.对于第三次是1入栈，1比6小所以我们直接入栈就好了，此时栈内元素还是最大值6，计算一下预算也就是 6 + 3 * （1 + 2 + 3） = 24 < 25所以还是可以，此时最大人数为3

4.对于第四次入栈，3比我们此时栈顶元素是1，可以发现3比1要大，如果直接入栈，不满足我们的单调性原则，所以我们要从栈顶弹出元素，直到遇到1个比3大的元素也就是6，所以此时栈内元素是6 3栈顶元素是3，此时计算一下预算，6 + 4 * （1 + 2 +3 + 4） = 46 <25 所以肯定是不合理的超出预算了，这个时候我们就要进行窗口的移动操作了，也就是我们左侧的端点l要进行右移了，这个时候我们就需要做个判断了，也就是我们刚才提到过的核心，如何去更新这个最大值，对应现在这个问题就很简单了，只需要判断栈底元素也就是最大元素（这里大家需要注意一下，我们每次要需要取出栈底最大值元素，所以我们最好的实现方式是使用双端队列去模拟，这样我们一端入栈，同时可以取出另一端的最大值元素）和我们的当前l位置的元素的关系，如果相等，那么弹出栈底元素（双端队列可以两侧操作），也就是代表此时需要去掉一个最大值元素，维护当前区间内的最大值，也就是栈底当前的元素，这样就实现了O(1)时间更新最大值（单调栈的魅力），自此本道题目的思路也就明了了。

实现代码（C++版本）如下：

class Solution {
public:
    int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
        int n = chargeTimes.size();
        
        int ans = 0, left = 0;

        long long sum = 0;
        deque<int> q;
        for(int i = 0;i < n; i++){
            while(!q.empty() && chargeTimes[i] >= chargeTimes[q.back()]){
                q.pop_back();//栈顶元素弹出，保证单调栈的实现
            }

            q.push_back(i);

            sum += runningCosts[i];

            while(!q.empty() && chargeTimes[q.front()] + (i - left + 1) * sum > budget){
                if(q.front() == left){
                    q.pop_front();//最大元素需要更新的时候
                }

                sum -= runningCosts[left++];//这里需要注意l更新之后sum也要更新
            }

            ans = max(ans, i - left + 1);
        }
        return ans;
    }
};