力扣-239题滑动窗口最大值（C++）- 有价值+单调队列

向右看齐 2022-09-12 07:47 293阅读 0赞

题目链接：[https://leetcode-cn.com/problems/sliding-window-maximum/][https_leetcode-cn.com_problems_sliding-window-maximum]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Solution {
        
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        
            vector<int> result;
            deque<int> q;//双端队列，存放下标
    
            for(int i=0;i<nums.size();i++){
        
                if(q.size()!=0&&i-k+1>q.front())//队列不为空，并且当前位置对应的左边界(i-k+1)
                    q.pop_front();//头删
    
                while(q.size()!=0&&nums[i]>=nums[q.back()])//队列不为空，且当前值大于左侧的值，则左侧的值可删除，无意义
                    q.pop_back();//尾删
    
                q.push_back(i);//放入队列
                
                if(i>=k-1)//表示当前窗口里有k个元素，因为每次移除一个，也会移入一个，即判断的范围每次都是k个 
                    result.push_back(nums[q.front()]);//存入返回数组
            }
    
            return result;
    
        }
    };

[https_leetcode-cn.com_problems_sliding-window-maximum]: https://leetcode-cn.com/problems/sliding-window-maximum/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/6c5c30a7500648ddb7c277dd8b04fc9f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/39147a77f05f4b49972d89070d1e5639.png