讨论/《图解算法数据结构》 - 剑指 Offer 59 - I. 滑动窗口的最大值/
《图解算法数据结构》 - 剑指 Offer 59 - I. 滑动窗口的最大值
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res={};
        deque<int> que={};
        for(int i=0;i<nums.size();i++)
        {
            //que保存最大值数组下标,不保存值
            //如果不为空而且,应该弹出的值刚好就是最大值,那么弹出
            //这时候最大值改为队列里原先第二大的数据
            if(!que.empty()&&que.front()==i-k)
            {
                que.pop_front();
            }
            //如果下一个要插入的数大于当前队列最小的数,
            //那么一直清空直到最后的数字大于新的数字
            //因为需要保证从大到小的顺序
            while(!que.empty()&&nums[i]>nums[que.back()])
            {
                que.pop_back();
            }
            //无论如何应该加入,因为如果大于的话,就要加入,
            //如果小于等于的话,也应该加入,因为我们要保证次大值小于等于最大值
            //而且这样的值应该被记录,不然就会跳到下一个更小的值
            que.push_back(i);
            //当数据足够凑成一组了之后,需要向输出容器中输入数据
            if(i>k-2)
            {
                res.push_back(nums[que.front()]);
            }
        }
        return res;
    }
};
展开全部 26 讨论