常见模型：找出滑动窗口中的最小值或最大值

1 题目

滑动窗口最大值） (leetcode-cn.com)

2 分析

要求：求固定长度滑动窗口内的最大值。

• 使用双端队列实现一个优先队列，只有新加入的数比队列尾的数大，我们就把队尾的数删除然后加入新的数。这样队列是一个单调递减的队列
• 队头元素就是滑窗内的最大值

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;   // 存储遍历元素的下标
        vector<int> res;
        for (int i = 0; i < nums.size(); i ++) {
            if (q.size() && i - q.front() + 1 > k) q.pop_front();  // 队头出队
            while(q.size() && nums[i] >= nums[q.back()]) q.pop_back();
            q.push_back(i);
            if (i >= k - 1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};

3 例子

待补充