预算内的最多机器人数目(Leetcode 2398)

题目分析

   本题是周赛的第四题，有一定的难度，考点非常多，如果能做好本题，那么基本的功力就可以达标了。本题涉及到的考点包含：二分查找、前缀和、单调栈、单调队列、双指针、滑动窗口。小伙伴不要害怕，先试试看。

双指针

本题可以使用二分查找+滑动窗口+单调队列+前缀和求解。求滑动窗口中的最大值，时间复杂度可以做到$ O(n) $，求前缀和，时间复杂度也可以做到$ O(n) $。二分查找的时间复杂度是 $ O(log(n)) $。算法的时间复杂度为$ O(nlog(n)) $，空间复杂度为O(n)。

上面这种做法小伙伴们可以尝试一下，可以参考leetcode239题。这里就不讲解了，这里讲一种更加高效的解法，双指针。

二分查找的局限性在于，滑动窗口的大小是固定的，这里是不是可以不固定呢？

下面就有两种思路：

1. 窗口右边一直向后遍历，找到最右侧不满足条件的索引。如果还有预算就一直向后查找，如果缺少预算，则剔除最左边的机器人，每次循环结束后最左边的索引+1。
2. 窗口右边每次向后移动一个位置，如果不满足条件，就一直剔除最左边的机器人，直到满足条件，每次循环结束后最右边的索引+1。

两个方法对比后发现方法二更好，因为方法1是查找不满足条件的最右侧的索引。假设某个元素不满足条件，还需要从队列中将其pop出来，防止下次进去时再次push进去。

算法的时间复杂度为$ O(n) $，空间复杂度为O(n)。

class Solution {
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        int n = chargeTimes.length;
        long cnt = 0;
        int res = 0;
        LinkedList<Integer> queue = new LinkedList<>();
        for (int left = 0, right = 0; right < n; right++) {
            cnt += runningCosts[right];
            while (!queue.isEmpty() && queue.peekLast() < chargeTimes[right]) {
                queue.pollLast();
            }
            queue.add(chargeTimes[right]);
            while (!queue.isEmpty() && (right - left + 1) * cnt + queue.peekFirst() > budget) {
                if (queue.peekFirst() == chargeTimes[left]) {
                    queue.pollFirst();
                }
                cnt -= runningCosts[left++];
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

刷题总结

  这个题目难度较大，需要小伙伴理解滑动窗口的写法。