单调栈

单调栈

单调为单调递增 / 单调递减，通过栈的方式找到单调增的顺序 / 单调减的顺序。

规则:
新元素入栈时，弹出破坏栈内单调性的栈顶元素。
出栈时触发计算(计算目标值)

Example:

• 接雨水
• 柱状图中的最大矩形
• 最高温度
• 下一个更大元素 I

模版:

    // 单调栈模板：计算 nums 中每个元素的下一个更小或相等的元素int[] nextLessOrEqualElement(int[] nums) {int n = nums.length;// 存放答案的数组int[] res = new int[n];Stack<Integer> s = new Stack<>();// 倒着往栈里放for (int i = n - 1; i >= 0; i--) {// 删掉 nums[i] 后面较大的元素while (!s.isEmpty() && s.peek() > nums[i]) {s.pop();}// 现在栈顶就是 nums[i] 身后的更小或相等元素res[i] = s.isEmpty() ? -1 : s.peek();s.push(nums[i]);}return res;}