C/C++教程

LeetCode 239 Sliding Window Maximum 单调队列 [Hard]

本文主要是介绍LeetCode 239 Sliding Window Maximum 单调队列 [Hard]，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

You are given an array of integers nums, there is a sliding window of size \(k\) which is moving from the very left of the array to the very right. You can only see the \(k\) numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Solution

求出在每个窗口的最大值。我们使用单调队列 \(O(n)\)，具体来说：

假设在位置 \(i\), 我们维护的区间为 \([i-k+1, i]\). 我们的单调队列维护的是下标 \(idx\)，所以如果队首的下标满足：

\[q.front<i-k+1 \]

则说明不在当前区间内，则 \(pop\) 出去。

由于我们只需要维护最大值，所以比当前元素小的都得 \(pop\_back()\)

点击查看代码 
class Solution {
private:
    vector<int> ans;
    deque<int> q;
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n=nums.size();
        
        for(int i=0;i<n;i++){
            // [i-k+1, i]: #ele = i-(i-k+1)+1 = k;
            if(q.front()<i-k+1 && !q.empty()) q.pop_front();
            
            while(!q.empty() && nums[q.back()]<nums[i])q.pop_back();
            q.push_back(i);
            if(i-k+1>=0)ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};
这篇关于LeetCode 239 Sliding Window Maximum 单调队列 [Hard]的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航