本博文所有的代码均可在 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]);
}
在上面的单调栈中,访问到任一个数组元素时,当前栈顶就是该元素的前上界(递增栈)或者前下界(递减栈)。
下面以实际算法题来说明递增栈的作用。
链接: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 + " ");
}
}
}
给定 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 res
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;
}
}
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;
}
}