862. 和至少为 K 的最短子数组

思路：
非典型单调队列
先维护一个前缀和
维护单调递增队列，遍历到当前元素x时，从队尾弹出比x大的元素y，因为后续能与y匹配的元素，与x也一定能匹配。
从队头开始处理，如果队头元素z与x满足x - z >= k时，更新结果，并将z从队头弹出，因为能与x匹配，没必要再与后面的元素再匹配，不会对结果造成影响。
每个元素只会进队出队一次，时间复杂度为O(n)
注意一开始会有个0被填入，表示从头到当前元素这一段。

  1. class Solution {
  2.     public int shortestSubarray(int[] nums, int k) {
  3.         int n = nums.length;
  4.         long[] pre = new long[n + 1];
  5.         for (int i = 1; i <= n; i++)
  6.             pre[i] = nums[i - 1] + pre[i - 1];
  8.         int[] q = new int[n + 1];
  9.         int hh = 0, tt = -1;
  11.         int res = 0x3f3f3f3f;
  12.         for (int i = 0; i <= n; i++) {
  13.             // System.out.println(hh + " " + tt);
  14.             while (hh <= tt && pre[i] - pre[q[hh]] >= k) {
  15.                 res = Math.min(res, i - q[hh]);
  16.                 hh++;
  17.             }
  18.             while (hh <= tt && pre[q[tt]] >= pre[i])
  19.                 tt--;
  21.             q[++tt] = i;
  22.         }
  23.         return res == 0x3f3f3f3f ? -1 : res;
  24.     }
  25. }

239. 滑动窗口最大值

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

示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
———————- ——-
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1 输出：[1]

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

思路：滑动窗口 + 双端单调队列

  1. class Solution {
  2. public:
  3.     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
  4.         int n = nums.size();
  5.         int stk[n];
  6.         int hh = 0, tt = -1;
  8.         vector<int> res;
  9.         for (int i = 0; i < n; i++) {
  10.             while (hh <= tt && nums[stk[tt]] <= nums[i])
  11.                 tt--;
  12.             if (hh <= tt && stk[hh] <= i - k)
  13.                 hh++;
  14.             stk[++tt] = i;
  15.             if (i >= k - 1)
  16.             res.push_back(nums[stk[hh]]);
  17.         }
  18.         return res;
  19.     }
  20. };

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

双端单调递减序列

  1. class Solution {
  2.     public int maximumRobots(int[] e, int[] w, long budget) {
  3.         int n = e.length;
  4.         int[] stk = new int[n];
  5.         int hh = 0, tt = -1;
  7.         long s = 0;
  8.         int max = 0;
  9.         for (int i = 0, j = 0; i < n; i++) {
  10.             s += w[i];
  11.             while (hh <= tt && e[stk[tt]] <= e[i])
  12.                 tt--;
  13.             stk[++tt] = i;
  15.             while (hh <= tt && s * (i - j + 1) > budget - e[stk[hh]]) {
  16.                 if (stk[hh] == j) hh++;
  17.                 s -= w[j];
  18.                 j++;
  19.             }
  20.             max = Math.max(max, i - j + 1);
  21.         }
  22.         return max;
  23.     }
  24. }