力扣labuladong——一刷day86

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

前言

单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。

一、力扣496. 下一个更大元素 I

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int a : nums1){
            map.put(a,0);
        }
        Deque<Integer> deq = new LinkedList<>();
        for(int i = nums2.length-1; i >= 0; i --){
            while(!deq.isEmpty() && deq.peekLast() <= nums2[i]){
                deq.pollLast();
            }
            if(map.containsKey(nums2[i])){
                map.put(nums2[i], deq.isEmpty() ? -1 : deq.peekLast());
            }
            deq.offerLast(nums2[i]);
        }
        int[] res = new int[nums1.length];
        for(int i = 0; i < nums1.length; i ++){
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}

二、力扣739. 每日温度

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        Deque<State> deq = new LinkedList<>();
        int[] res = new int[n];
        for(int i = n-1; i >= 0; i --){
            while(!deq.isEmpty() && deq.peekLast().t <= temperatures[i]){
                deq.pollLast();
            }
            res[i] = deq.isEmpty() ? 0 : deq.peekLast().id - i;
            deq.offerLast(new State(temperatures[i],i));
        }
        return res;
    }
    class State{
        int t;
        int id;
        public State(int t, int id){
            this.t = t;
            this.id = id;
        }
    }
}