Leetcode 239. 滑动窗口最大值

题目：https://leetcode-cn.com/problems/sliding-window-maximum/

单调队列可以实现O(n).

class Solution {
public:
struct data{
    int data;
    int position;
};
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<data>de;
    int len=nums.size();
    vector<int>res;
    for(int i=0;i<len;i++){
        while(!de.empty() && de.back().data < nums[i]) // 出队尾直到第一个大于目前的数
        {
            de.pop_back();
        }
        de.push_back(data{nums[i], i});
        if (i - de.front().position >= k)//超出k范围的出队
        {
            de.pop_front();
        }
        if(i >= k-1) //从k-1开始计数
        {
            res.push_back(de.front().data);
        }
    }
    return res;
    }
};