栈-EmiyaCC 摘录室

单调栈
- 数组元素不重复
  - 下一个更大元素 I
- 数组元素重复
  - 下一个更大元素 II
  - 每日温度

单调栈

单调栈是一种特殊的栈，每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。主要解决 Next Great Number 一类算法问题

数组元素不重复

对于数组元素不重复且需要取对应键值对的情况，可以利用 Stack 存储不符合单调规律的元素，并利用 HashMap 来存储需要的递增对应关系

// 这种做法适合数组元素不重复的
class Solution {
	public HashMap<E> function(E[] nums) {
        Map<E, E> map = new HashMap<>();
        Stack<E> stack = new Stack<>();
        // 下面是将 <元素，下一个更大元素> 存入 map 中
        // 注意如果该元素最大，组不存入 map 中，同时最后一个元素并没有存入，对于这些未存入的 元素，可以使用 map.getOrDefault() 函数，赋予其一个值
        int len = nums.length;
        for (int i = 0; i < len; i ++) {
            while (!stack.isEmpty() && stack.peek() < nums[i]) {
                map.put(stack.pop(), nums[i]);
            }
            stack.push(nums[i]);
        }
        // 这里是操作。。。
        return map;
    }
}

下一个更大元素 I

本题没有重复元素，所以基本是对抄模板就ok

// https://leetcode-cn.com/problems/next-greater-element-i/
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        int len2 = nums2.length;
        for (int i = 0; i < len2; i ++) {
            while (!stack.isEmpty() && stack.peek() < nums2[i]) {
                map.put(stack.pop(), nums2[i]);
            }
            stack.push(nums2[i]);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i ++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }
}

数组元素重复

对于数组中元素有重复的情况，所以不能用 HashMap 来记录键值对，所以需要利用下标，先记录对应位置的下一个更大值的下标，再利用数组记录下来，上面 Stack 是用来存数组中的元素，而这里的 Stack 是来存数组中元素对应的下标。模板：

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                res[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        return res;
    }
}
// 链接：https://leetcode-cn.com/problems/next-greater-element-ii/solution/xia-yi-ge-geng-da-yuan-su-ii-by-leetcode-bwam/

下一个更大元素 II

相对于上题，本题区别是有重复元素，所以不能用 HashMap 来记录键值对

// https://leetcode-cn.com/problems/next-greater-element-ii/
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n * 2 - 1; i ++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                res[stack.pop()] = nums[i % n]; 
            }
            stack.push(i % n);
        }
        return res;
    }
}

每日温度

本题对比上题，区别是，上题是求下一个更大值的值，而本题是求下个一更大值间隔距离，其实本质是一样的

// (https://leetcode-cn.com/problems/daily-temperatures/
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        Arrays.fill(res, 0);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i ++) {
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                // 区别在于这里是记录下原值的下标，然后两个下标相减，求得两个值之间的间隔距离
                int cur = stack.pop();
                res[cur] = i - cur;
            }
            stack.push(i);
        }
        return res;
    }
}

Reference：

https://labuladong.gitee.io/algo/

https://leetcode-cn.com/problems/