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

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

article 2024/9/25 15:29:51

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

题意：

在这里插入图片描述

解析：

需要注意的是，题目询问中连续是子数组的意思，即求满足条件的最长子数组的长度。

因为是连续的，所以可以用双指针扫描整个数组。每次将右指针 $r$ 向右移动一个位置，然后左指针 $l$ 向右移动到满足 budget 限制的位置。

判断区间 [l,r] 是否满足budget 限制。在扫描时，可以用一个变量维护区间 cost 的和，也可以通过前缀和来得到 sum(cost)。除此之外，需要这段区间 times 的最大值，维护一个非严格递减的单调队列，队首元素是这段区间 times 的最大值。

在将左指针 $l$ 右移的时候，需要判断单调队列队首元素是否已经失效。

代码：

int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
        int n = chargeTimes.size();
        deque<int> q;
        long long sum = 0;
        int ans = 0;
        for(int l = 0, r = 0; r < n; r++){
            sum += runningCosts[r];
            while(q.size() && chargeTimes[q.back()] < chargeTimes[r])
                q.pop_back();
            q.push_back(r);
            while(q.size() && chargeTimes[q.front()] + (r-l+1) * sum > budget){
                sum -= runningCosts[l++];
                if(q.front() < l)
                    q.pop_front();                 
            }
            ans = max(ans, r-l+1);
        }
        return ans;
    }