当前位置：首页 > article >正文

力扣 239. 滑动窗口最大值

article 2024/11/25 11:05:58

🔗 https://leetcode.cn/problems/sliding-window-maximum

题目

给定一个数组，给定数字 k，滑动窗口的大小为 k，从数组的头往后移动
返回每个窗口内的最大值

思路

单调队列的经典场景
用双向队列记录，队列的头是滑动窗口内的最大值的 index，该队列保证 nums[index] 降序
通过判断当前 index 与队列头的 index 的间隔，判断是否在滑动窗口内，不再则 pop front，因为队列是降序的，保证了后续索引纸箱的数字，是当前滑动窗口内的最大值
为了保证队列索引表示的数字是降序，判断队列尾部的数字是否比当前元素大，若不大，则 pop back，记录当前元素，从尾部入队列

代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++) {
            while (!dq.empty() && i - dq.front() >= k) {
                dq.pop_front();
            } 

            while (!dq.empty() && nums[dq.back()] <= nums[i]) {
                dq.pop_back();
            }

            dq.push_back(i);

            if (i >= k-1) {
                ans.push_back(nums[dq.front()]);
            }
            
        }
        return ans;
    }
};