单调栈详解及其LeetCode应用详解
本博文所有的代码均可在 https://github.com/Hongze-Wang/LeetCode_Java https://github.com/Hongze-Wang/LeetCode_Python 中找到。
栈(Stack)是一种操作受限的线性表，只允许一端进，同一端出，因而具有后进先出(LIFO)的特性。
单调栈(Monotonic Stack)是一种特殊的栈，它首先是一个栈，其次栈中的所有元素单调递增或者单调递减。
单调栈在算法中的应用在于它能够在一次扫描即O(n)的复杂度之内找到数组中每一个元素的前上界(单增栈)或者前下界(单减栈)。
// 递增栈
for(int i=0; i<arr.length; i++) {
while(!stack.empty() && stack.peek() >= arr[i]) {
stack.pop();
}
stack.push(arr[i]);
}
// 递减栈
for(int i=0; i<arr.length; i++) {
while(!stack.empty() && stack.peek() <= arr[i]) {
stack.pop();
}
stack.push(arr[i]);
}在上面的单调栈中，访问到任一个数组元素时，当前栈顶就是该元素的前上界(递增栈)或者前下界(递减栈)。
下面以实际算法题来说明递增栈的作用。
[编程题]逛街 腾讯2020秋招真题
链接：https://www.nowcoder.com/question/next?pid=21283868&qid=830860&tid=37511217 来源：牛客网
时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M 小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。 小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住） 输入描述: 输入第一行将包含一个数字n，代表楼的栋数，接下来的一行将包含n个数字wi(1<=i<=n)，代表每一栋楼的高度。 1<=n<=100000; 1<=wi<=100000; 输出描述: 输出一行，包含空格分割的n个数字vi，分别代表小Q在第i栋楼时能看到的楼的数量。 示例1 输入 6 5 3 8 3 2 5 输出 3 3 5 4 4 4 说明 当小Q处于位置3时，他可以向前看到位置2,1处的楼，向后看到位置4,6处的楼，加上第3栋楼，共可看到5栋楼。当小Q处于位置4时，他可以向前看到位置3处的楼，向后看到位置5,6处的楼，加上第4栋楼，共可看到4栋楼。
// 递减栈 栈中元素数目即为能看到的楼数目
// 两个栈 一个表示向左能看到的数目 一个表示向右 注意所有栈都不考虑当前所在楼本身 因此最后结果要加1
// 以向右看为例
// 单调栈里维护了从最左边到该位置前递减序列 而到达当前位置的递减序列对于当前位置来 都是可见的
// 因此单调栈的大小保存了能看到楼的个数
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
public class Tencent2020backend2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] height = new int[n];
for(int i=0; i<n; i++) {
height[i] = sc.nextInt();
}
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
ArrayList<Integer> count1 = new ArrayList<>();
ArrayList<Integer> count2 = new ArrayList<>();
for(int i = 0, j = height.length-1; i < height.length && j>=0; i++, j--) {
count1.add(stack1.size());
count2.add(0, stack2.size());
while(!stack1.empty() && stack1.peek() <= height[i]) stack1.pop();
while(!stack2.empty() && stack2.peek() <= height[j]) stack2.pop();
stack1.push(height[i]);
stack2.push(height[j]);
}
for(int i=0; i<n; i++) {
System.out.print(count1.get(i) + count2.get(i) + 1 + " ");
}
}
}84. Largest Rectangle in Histogram (hard)
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。 示例: 输入: [2,1,5,6,2,3] 输出: 10
我下面给出的解法比官方题解还要简洁，注意栈中存的是索引而不是元素，因为要作为宽度计算面积：
# 递增栈
# 每次遇到非递增元素 可以计算一次面积 在所有计算的面积中找到最大的即可
# 巧妙的利用了递增栈的性质
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = [-1]
heights.append(-1)
res = 0
for idx, val in enumerate(heights):
while heights[stack[-1]] > val:
h = heights[stack.pop()]
res = max(res, h*(idx - stack[-1]-1)) # idx-stack[-1]-1是当前递增序列的宽度
stack.append(idx)
return res42. Trapping Rain Water (hard)
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Example 2:
Input: height = [4,2,0,3,2,5] Output: 9
Constraints:
n == height.length 0 <= n <= 3 * 104 0 <= height[i] <= 105
// 单调栈 递减栈
// 分析题意 不难看出我们需要找到当前元素的左上界 和 右上界 因而使用单调栈
// 这里使用递减栈 注意 一定要想清楚使用递增栈还是递减栈
class Solution {
public int trap(int[] height) {
int res = 0, idx = 0;
Stack<Integer> stack = new Stack<>();
while(idx < height.length) {
while(!stack.isEmpty() && height[idx] > height[stack.peek()]) {
int top = stack.pop();
if(stack.isEmpty()) {
break;
} else{
int dis = idx-stack.peek()-1;
int h = Math.min(height[idx], height[stack.peek()]) - height[top];
res += dis * h;
}
}
stack.push(idx++);
}
return res;
}
}
// for循环和单调栈模板代码更接近
class Solution {
public int trap(int[] height) {
int res = 0;
Stack<Integer> stack = new Stack<>();
for(int idx = 0; idx < height.length; idx++) {
while(!stack.isEmpty() && height[idx] > height[stack.peek()]) { // 模板代码 维护一个递减栈 注意不是大于等于
int top = stack.pop(); // 模板代码 维护一个递减栈
if(stack.isEmpty()) {
break;
} else{
int dis = idx-stack.peek()-1; // 上界本身不能存贮雨水
int h = Math.min(height[idx], height[stack.peek()]) - height[top];
res += dis * h;
}
}
stack.push(idx); // 模板代码 维护一个递减栈
}
return res;
}
}503. Next Greater Element II (Medium)
Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, output -1 for this number.
Example 1: Input: [1,2,1] Output: [2,-1,2] Explanation: The first 1’s next greater number is 2; The number 2 can’t find next greater number; The second 1’s next greater number needs to search circularly, which is also 2.
// 分析题目不难看出解法要使用单调栈
// 找下一个更大元素可以通过从右向左构造递减栈来实现 递减栈保存了比当前元素更大的元素 如果当前元素最大 则递减栈为空
// 从右向左构造递减栈相当于从左向右找下一个最大的数 如果这个方向找不到可能要尝试从右向左找
// 但循环数组是一个痛点
// 联系到循环队列的数组实现是使用模运算来实现循环的 可以参考借鉴一下
// 例：nums.lenght = 5 for(int i=2*nums.length-1; i>=0; i--)
// 得到的索引序列是9 8 7 6 5 4 3 2 1
// i % nums.length的结果是 4 3 2 1 0 1 2 3 4 即为我们所需要的查找顺序
// 可以应用到这一题
class Solution {
public int[] nextGreaterElements(int[] nums) {
int[] res = new int[nums.length];
Stack<Integer> stack = new Stack<>();
for(int i=2*nums.length-1; i>=0; i--) {
while(!stack.isEmpty() && nums[stack.peek()] <= nums[i % nums.length]) { // 递减栈模板代码 维护一个递减栈
stack.pop(); // 递减栈模板代码 维护一个递减栈
}
res[i % nums.length] = stack.isEmpty() ? -1 : nums[stack.peek()];
stack.push(i % nums.length); // 递减栈模板代码 维护一个递减栈
}
return res;
}
}