力扣labuladong一刷day51天单调栈应用

力扣labuladong一刷day51天单调栈应用

一、239. 滑动窗口最大值

题目链接：https://leetcode.cn/problems/sliding-window-maximum/
思路：滑动窗口最大值，既要维护加入的时间顺序，又要

class Solution {
   public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        Queue queue = new Queue();
        for (int i = 0; i < k; i++) {
            queue.push(nums[i]);
        }
        int j = 0;
        res[j++] = queue.getMax();
        for (int i = k; i < nums.length; i++) {
            queue.pop(nums[i-k]);
            queue.push(nums[i]);
            res[j++] = queue.getMax();
        }
        return res;
    }

    class Queue {
        LinkedList<Integer> stack = new LinkedList<>();
        void push(int n) {
            while (!stack.isEmpty() && n > stack.getLast()) {
                stack.pollLast();
            }
            stack.addLast(n);
        }
        void pop(int n) {
            if (n == stack.getFirst()) {
                stack.pollFirst();
            }
        }
        int getMax() {
            return stack.getFirst();
        }
    }
}