单调队列
类似单调栈，就是一个「队列」，只是使用了一点巧妙的方法，使得队列中的元素全都是单调递增（或递减）的。可以解决滑动窗口相关的问题。
滑动窗口最大值
对于滑动窗口，最主要是是记录窗口内的最大值。假设有 i 和 j 下标（i < j），对应 nums[i] 和 nums[j]（nums[i] <= nums[j]），那么 i 下标对应的值肯定是比 j 下标对应的值先出窗口，也就是说 i 和 j 存在的场合，i 对应的值 nums[i] 其实是不需要记录的，因为最大值肯定是 nums[j]
由于滑动窗口以下标操作位置，所以建议 Stack 记录下标（单调栈中，下一个更大值1 主要是对值操作，所以记录值，下一个更大值2 和 每日温度，主要是对下标操作，所以记录下标）
本题需要对比队列前面的值和后面的值，所以需要用到 Deque
// https://leetcode-cn.com/problems/sliding-window-maximum/
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new LinkedList<>();
int len = nums.length;
for (int i = 0; i < k; i ++) {
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
}
int[] res = new int[len - k + 1];
res[0] = nums[deque.peekFirst()];
for (int i = k; i < len; i ++) {
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
// 如果 deque 中的下标划出窗口了
while (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
res[i - k + 1] = nums[deque.peekFirst()];
}
return res;
}
}
Reference：
- https://labuladong.gitee.io/algo/
- https://leetcode-cn.com/problems/