Leetcode记录：单调队列
单调队列
队列和双端队列这里不再赘述，对应的数据结构是queue和deque，前者只支持输出队首和插入队尾，但后者支持双端的输出和插入。deque支持迭代器但queue和stack不支持迭代器。
单调队列是一个限制只能队尾插入，但是可以两端删除的双端队列。单调队列存储的元素值，是从队首到队尾呈单调性的（要么单调递增，要么单调递减）。对于求解最大值的问题，则需要维护一个单调递减的队列。
获取队首元素
由于单调队列是单调递减的，所以队首元素最大，直接$O(1)$获取队首元素。
删除
删除分为队首删除和队尾删除。队首删除即直接队首元素出队，$O(1)$即可完成操作。队尾删除一般是配合队尾插入进行的。
插入
在进行队尾插入的时候，我们往往需要明白一个重要的点，就是需要保证它单调递减的性质，所以如果队尾元素$\leq$插入元素，则当前的队尾元素是需要执行删除操作的（也就是上文提到的队尾删除），直到满足队尾元素$>$插入元素，才能真正执行插入操作。
这样才能保证，执行队尾插入后，单调队列仍然是单调递减的。插入过程，虽然伴随着元素的删除，但是每个元素至多被插入一次和删除一次，所以均摊时间复杂度还是$O(1)$的。
性质
- 保序性 由于单调队列执行插入的时候，一定是从队尾进行插入，所以单调队列中的数据，从队首到队尾的顺序，一定是和原序列严格保序的；
- 下标存储 为了让单调队列的数据足够干净，在单调队列中，一般存储 原序列的下标 即可，而不需要存储原序列的值，根据保序性，存储的下标一定是单调递增的；
- 单调性 单调队列中的元素是 原序列的下标，对应到原序列时，根据求解问题的不同，当需要求最大值时，它是单调递减的；当需要求最小值时，它是单调递增的；
单调队列的典型应用是在滑动窗口中寻找最大/最小值的问题。
滑动窗口最大值
Leetcode 239. 给你一个整数数组nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值。 重要的是单调性分析： 如果当前的滑动窗口中有两个下标 $i$ 和 $j$，其中 $i$ 在 $j$ 的左侧($i<j$)，并且 $i$ 对应的元素不大于 $j$ 对应的元素($nums[i]\leq nums[j]$),当滑动窗口向右移动时，只要 $i$ 还在窗口中，那么 $j$ 一定也还在窗口中，这是 $i$ 在 $j$ 的左侧所保证的。因此，由于 $nums[j]$ 的存在，$nums[i]$ 一定不会是滑动窗口中的最大值了，我们可以将 $nums[i]$ 永久地移除。
因此我们可以使用一个队列存储所有还没有被移除的下标。在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组 nums 中对应的值是严格单调递减的。因为如果队列中有两个相邻的下标，它们对应的值相等或者递增，那么令前者为 $i$，后者为 $j$，就对应了上面所说的情况，即 $nums[i]$ 会被移除，这就产生了矛盾。
当滑动窗口向右移动时，我们需要把一个新的元素放入队列中。为了保持队列的性质，我们会不断地将新的元素与队尾的元素相比较，如果前者大于等于后者，那么队尾的元素就可以被永久地移除，我们将其弹出队列。我们需要不断地进行此项操作，直到队列为空或者新的元素小于队尾的元素。
由于队列中下标对应的元素是严格单调递减的，因此此时队首下标对应的元素就是滑动窗口中的最大值。但此时的最大值可能在滑动窗口左边界的左侧，并且随着窗口向右移动，它永远不可能出现在滑动窗口中了。因此我们还需要不断从队首弹出元素，直到队首元素在窗口中为止。
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
deque<int> q;
for (int i = 0; i < k; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
}
vector<int> ans = {nums[q.front()]};
for (int i = k; i < n; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
while (q.front() <= i - k) {
q.pop_front();
}
ans.push_back(nums[q.front()]);
}
return ans;
}
和至少为k的最短子数组
Leetcode 862. 给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。 单调性分析： 首先要使用前缀和处理，对于边界情况 $preSumArr[0] = 0$。而从数组 $nums$ 下标 $i$ 开始长为 $m$ 的子数组的和就可以根据 $preSumArr[i+m]−preSumArr[i]$ 快速计算得到。
遍历 $preSumArr$ 数组，访问过的前缀和先暂存在某种集合 $q$ 中。根据前缀和数组的性质，后访问到的某个前缀和 $preSumArr[j]$ 减去之前访问到的某个前缀和 $preSumArri$ 即为 $nums$ 中某段子数组的和。因此，每次访问到某个前缀和 $preSumArr[j]$ 时，可以用它尝试减去集合 $q$ 中所有已经访问过的前缀和。当某个 $q$ 中的前缀和 $preSumArr[i]$，第一次出现 $preSumArr[j]−preSumArr[i]\geq k$ 时，这个下标 $i$ 就找到了以它为起点的最短子数组的长度 $j−i$。此时，可以将它从 $q$ 中移除，后续即使还有以它为起点的满足条件的子数组，长度也会大于当前的长度。
当一个前缀和 $preSumArr[j]$ 试减完 $q$ 中的元素时，需要将它也放入 $q$ 中。将它放入 $q$ 前， $q$ 中可能存在比 $preSumArr[j]$ 大的元素，而这些元素和 $preSumArr[j]$ 一样，只能作为再后续访问到的某个前缀和 $preSumArr[h]$ 的减数。而作为减数时，更大的值只会让不等式 $preSumArr[h]−preSumArr[i]\geq k$ 更难满足。即使都满足，后访问到的值也可以带来更短的长度。 因此，在把 $preSumArr[j]$ 放入 $q$ 时，需要将 $q$ 中大于等于 $preSumArr[j]$ 的值也都移除。
接下来考虑 $q$ 的性质。我们会往 $q$ 中增加和删除元素。每次增加一个元素 $curSum$ 前，先根据不等式删除一部分元素（也可能不删），然后再删除 $q$ 中所有大于等于 $curSum$ 的元素，这样每次加进去的元素都会是 $q$ 中的唯一最大值，使得 $q$ 中的元素是按照添加顺序严格单调递增的。
int shortestSubarray(vector<int>& nums, int k) {
int n = nums.size();
vector<long> preSumArr(n + 1);
for (int i = 0; i < n; i++) {
preSumArr[i + 1] = preSumArr[i] + nums[i];
}
int res = n + 1;
deque<int> qu;
for (int i = 0; i <= n; i++) {
long curSum = preSumArr[i];
while (!qu.empty() && curSum - preSumArr[qu.front()] >= k) {
res = min(res, i - qu.front());
qu.pop_front();
}
while (!qu.empty() && preSumArr[qu.back()] >= curSum) {
qu.pop_back();
}
qu.push_back(i);
}
return res < n + 1 ? res : -1;
}