59-1滑动窗口的最大值

59-1滑动窗口最大值

题目给出的代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {       
    }
};

这里给出BF算法和利用deque维护的降序队列算法

BF是自己写的

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int>ans;
        if(nums.empty())
            return ans;
        for(int i = 0;i<nums.size()-k+1;i++)//一共输出n-k+1次
        {
            stack<int>s;//每次都初始化s
            for(int j = i;j<i+k;j++)//每次都从下标i开始
            {	
                if(s.empty())
                {
                    s.push(nums[j]);
                }
    //栈中一直维持着最大值，但这样栈的存在其实就没意思了，定一个max应该就可以
                if(!s.empty()&&nums[j]>s.top())
                {
                    s.pop();
                    s.push(nums[j]);
                }
            }
            //最后每次把栈顶放入数组
            ans.push_back(s.top());
        }
        return ans;
    }
};

但是用deque维护一个递减栈更好

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
       vector<int> ans;
       deque<int> deq;
       int n = nums.size();
       //我们要把数组的下标放到deque中去 
        //方便起见，我们把deque中的数代指vector中的数
        for (int i = 0; i < n; i++){
		//每次进来的如果比deque中的所有数要大，尾部比它小的都要清空
            while(!deq.empty() && nums[i] > nums[deq.back()]){
                deq.pop_back();
            }
            //一共要循环i-k+1次，所以当deq.front()到达i-k+1就不再进行循环了
            if (!deq.empty() && deq.front() < i - k + 1) deq.pop_front();
            //每次都需要把下标压入deque
            deq.push_back(i);
            //因为前几次，deque.front()还没有移动到vector[0],所以不能算
            if (i >= k -1) ans.push_back(nums[deq.front()]);
        }
        return ans;

    }
};