[数据结构]单调队列

单调队列常见模型：找出滑动窗口中的最大值/最小值。模板：

q = deque()
for i in range(n):
    # 判断队头是否滑出窗口
    while q and checkout_out(q[0]):
        q.popleft()
    while q and check(q[-1]):
        q.pop()
    q.append(i)

在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组 nums 中对应的值是严格单调递减的。

239. 滑动窗口最大值

滑动窗口的位置                  queue            最大值           
---------------               -----                        -------
[1  3  -1] -3  5  3  6  7     [ 1, 2 ]          3             
 1 [3  -1  -3] 5  3  6  7     [ 1, 2, 3 ]       3                            
 1  3 [-1  -3  5] 3  6  7     [ 4 ]             5
 1  3  -1 [-3  5  3] 6  7     [ 4, 5 ]          5
 1  3  -1  -3 [5  3  6] 7     [ 6 ]             6
 1  3  -1  -3  5 [3  6  7]    [ 7 ]             7

当滑动窗口向右移动时，我们需要把一个新的元素放入队列中。为了保持队列的性质，我们会不断地将新的元素与队尾的元素相比较，

• 如果前者大于等于后者，那么队尾的元素就可以被永久地移除，我们将其弹出队列。

我们需要不断地进行此项操作，直到队列为空或者新的元素小于队尾的元素。

function maxSlidingWindow(nums: number[], k: number): number[] {
    let queue = [];
    for (let i = 0; i < k; i++) {
        while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) {
            queue.pop();
        }
        queue.push(i);
    }
    let ans = [nums[queue[0]]];
    for (let i = k; i < nums.length; i++) {
        while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) {
            queue.pop();
        }
        queue.push(i);
        while (queue[0] <= i - k) {
            queue.shift();
        }
        ans.push(nums[queue[0]]);
    }
    return ans;
};