239. 滑动窗口最大值

[Ni-Guvara]

class MyQueue{
    private:
        deque<int> que;
    public:
        int push(int value)
        {
            while( !que.empty() && value > que.back())
                que.pop_back();

            que.push_back(value);

            return 0;
        }

        void pop(int value)
        {
            if(!que.empty() && que.front() == value)
                que.pop_front();
        }

        // 获取队列前端数据
        int front()
        {
            return que.front();
        }
};

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

        vector<int> ret;             // 返回数据

        MyQueue que;                 // 辅助数据
        int len = nums.size();       

        for(int idx = 0; idx < len; idx++)
        {
            if(idx < k)
            {
                que.push(nums[idx]);
                if(idx == k-1)
                    ret.push_back(que.front());        
                continue;       
            }else{
                que.pop(nums[idx-k]);
                que.push(nums[idx]);
            }

            ret.push_back(que.front());
        }
        return ret;              
    }
};

[rocksc30]

class MyQueen{
    LinkedList<Integer> quee = new LinkedList<>();

    void push(int n){
        while(!quee.isEmpty() && quee.getLast() < n){
            quee.pollLast();
        }
        quee.addLast(n);
    }

    int max(){
        return quee.getFirst();
    }
    void pop(int n){
        if (n == quee.getFirst()){
            quee.pollFirst();
        }
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        MyQueen myQueen = new MyQueen();
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            if (i < k - 1){
                myQueen.push(nums[i]);
            }else {
                // 窗口前移, 加入新数字
                myQueen.push(nums[i]);
                // 记录当前窗口的最大值
                res.add(myQueen.max());
                // 移除旧数字
                myQueen.pop(nums[i - k + 1]);
            }
        }
        int[] ret = new int[res.size()];
        for (int i = 0; i < ret.length; i++){
            ret[i] = res.get(i);
        }
        return ret;
    }
}