单调栈

单调栈：以一种策略入栈出栈，保持栈内元素单调; 通常用于解决满足某个条件的下一个元素问题(Next Greater Element问题);

如：一个数组，找到每个元素的后续最近的更大元素；保持栈单调递增，即每次元素入栈，栈顶元素都是比当前元素要大，也就是栈顶元素就是当前元素的下一个更大元素；

public int[] nextGreaterElement(int[] nums) {

    Stack<Integer> stack = new Stack<>();
    int[] nextGreaterArray = new int[nums.length];

    for (int i = nums.length - 1; i >= 0; i--) {
        // 比较栈顶，如不满足单调，则pop出栈
        while (!stack.isEmpty() && nums[i] > stack.peek()) {
            stack.pop();
        }
        // 处理当前元素,这里是记录当前元素的next greater
        int nextGreater = stack.isEmpty() ? -1 : stack.peek();
        nextGreaterArray[i] = nextGreater;
        // 当前元素入栈
        stack.push(nums[i]);
    }
    ...
}

针对不同问题场景，以不同的方式处理next element，如：哈希表、记录数值、记录索引等；

Leetcode：单调栈

单调栈