leetcode-剑指offer59-I 滑动窗口的最大值

大家好，又见面了，我是你们的朋友全栈君。

2020-8-13

这道题我实在没想到什么好方法，就暴力求解了。看了题解才知道stl里面还有双端队列这个数据结构，可是还是没看懂大佬们怎么用，只知道大概是维护了一个最小栈。等过几天更新大佬们的解法。

https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

暴力解法

class Solution {
public:
    int get_Max(queue<int> que)
    {
        int max_num = que.front();
        while(!que.empty())
        {
            max_num = max(que.front(), max_num);
            que.pop();
        }
        return max_num;
    }

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        queue<int>que;
        vector<int>ans;
        if(nums.empty())
            return ans;
        int max_num = nums[0];
        for(int i=0;i<k;i++)
        {
            que.push(nums[i]);
            max_num = max(max_num, nums[i]);
        }
        
        ans.push_back(max_num);
        for(int i=1;i+k<=nums.size();i++)
        {
            que.pop();
            que.push(nums[i+k-1]);
            if(nums[i-1] == max_num)
            {
                max_num = get_Max(que);
            }
            else
                max_num = max(nums[i+k-1], max_num);
            ans.push_back(max_num);
        }
        return ans;
    }
};