本文共 1057 字，大约阅读时间需要 3 分钟。

题目

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例一

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

滑动窗口的位置 最大值

[1 3 -1] -3 5 3 6 7 3

思路

• 我们维护一个不严格递减的单调队列。对于这个队列来说，队列里面存储的是原数组的下标。为什么存下标而不存原数组的数值，因为我们需要始终维护一个长度为k的窗口。
• 队列头每次是维护当前窗口里面的最大值。
• 新访问到一个元素：第一种情况，如果当前元素离目前的最大值的长度是在我们的窗口里面，此时我们需要判断元素和目前最大值的大小关系；第二种情况，超出窗口范围，先把前面不在范围的元素清出队列，继续比较大小关系。

代码

class Solution {
   public:    vector
   
     maxSlidingWindow(vector
    
     & nums, int k) {
           deque
     
       myq;        int n = nums.size();        vector
      
        ans;        if(n == 0) return ans;        for(int i = 0;i < n;i++){
               while(!myq.empty() && i - myq.front() + 1 > k){
                   myq.pop_front();            }            while(!myq.empty() && nums[i] >= nums[myq.back()]){
                   myq.pop_back();            }            myq.push_back(i);            if(i > k - 2) ans.push_back(nums[myq.front()]);        }        return ans;    }};
      
     
    
   

转载地址：https://blog.csdn.net/free1993/article/details/114916758 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！