力扣labuladong——一刷day87

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

现在需要一种新的队列结构，既能够维护队列元素「先进先出」的时间顺序，又能够正确维护队列中所有元素的最值，这就是「单调队列」结构。

一、力扣503. 下一个更大元素 II

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] arr = new int[2*n];
        int[] res = new int[n];
        for(int i = 0; i < 2*n; i ++){
            if(i < n){
                arr[i] = nums[i];
            }else{
                arr[i] = nums[i-n];
            }
        }
        Deque<Integer> deq = new LinkedList<>();
        for(int i = 2*n-1; i >= 0; i --){
            while(!deq.isEmpty() && deq.peekLast() <= arr[i]){
                deq.pollLast();
            }
            if(i < n){
                res[i] = deq.isEmpty() ? -1 : deq.peekLast();
            }
            deq.offerLast(arr[i]);
        }
        return res;
    }
}

二、力扣239. 滑动窗口最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        MonotonicDeque mq = new MonotonicDeque();
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < nums.length; i ++){
            if(i < k-1){
                mq.push(nums[i]);
            }else{
                mq.push(nums[i]);
                list.add(mq.getMax());
                mq.remove(nums[i-k+1]);
            }
        }
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size() ; i ++){
            res[i] = list.get(i);
        }
        return res;
    }
    class MonotonicDeque{
        LinkedList<Integer> deq;
        public MonotonicDeque(){
            this.deq = new LinkedList<Integer>();
        }
        public void push(int x){
            while(!deq.isEmpty() && deq.getLast() < x){
                deq.pollLast();
            }
            deq.addLast(x);
        }
        public int getMax(){
            return deq.getFirst();
        }
        public void remove(int x){
            if(!deq.isEmpty() && deq.getFirst() == x){
                deq.pollFirst();
            }
        }
    }
}