单调栈

date

Jan 6, 2022

slug

MonotoneStack

status

Published

单调栈

简介

单调栈是一种特殊的栈。栈本来就是一种受限的数据结构了，单调栈在此基础上又受限了一次。

单调栈要求栈中的元素是单调递增或者单调递减的。

例

[a,b,c] 表示一个栈。其中左侧为栈底，右侧为栈顶。

单调增还是单调减取决于出栈顺序。如果出栈的元素是单调增的，那就是单调递增栈，如果出栈的元素是单调减的，那就是单调递减栈。

[1,2,3] 就是一个单调递减栈

[3,2,1] 就是一个单调递增栈

[1,3,2] 就不是一个合法的单调栈

适应场景

单调栈适合的题目是求解 下一个大于 xxx 或者 **下一个小于 xxx **这种题目。

构建

要依次将数组 [1,3,4,5,2,9,6] 压入单调栈

首先压入 1，此时的栈为：[1]

继续压入 3，此时的栈为：[1,3]

继续压入 4，此时的栈为：[1,3,4]

继续压入 5，此时的栈为：[1,3,4,5]

如果继续压入 2，此时的栈为：[1,3,4,5,2] 不满足单调递减栈的特性，因此需要调整。

查看栈顶是否小于 2 ，如果大于2，弹出栈顶，直到小于2，压入2入栈

模板

public int[] nextGreaterElement(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int[] result = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= nums[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? 0 : stack.peek();
            stack.add(nums[i]);
        }
        return result;
  }