栈有先进后出的特性,是一个很常用的数据结构。
顾名思义单调栈是栈内元素是单调的,即递增或递减的,
若栈顶到栈底的序列是递增的(即按出栈的顺序),则称为单调递增栈;
若栈顶到栈底的序列是递减的(即按出栈的顺序),则称为单调递减栈。
以单调递增栈为例,它具有以下特性
- 栈顶的元素始终比栈内元素小;
- 新元素入栈时,需要将栈内比新元素小的元素出栈,然后在将新元素入栈,以保持栈内单调性。
单调栈有什么用呢? 单调栈旨在解决在线性时间复杂度内寻找一个序列中每个元素的边界问题。
# 经典例题
# 寻找下一个更大的元素
给定数组nums,找到nums中每个元素的下一个比其大的值。 对于在nums中的元素x的下一个更大元素是向右寻找第一个比其大的值,如果不存在,对应位置输出-1。 示例:
输入:nums = [1,5,7,2,3]
输出:[5,7,-1,3,-1]
解释:
对于nums中的数字1,其右边第一个比其大的值为5;
对于nums中的数字5,其右边第一个比其大的值为7;
对于nums中的数字7,其右边不存在比其大的数,因此对应位置为-1;
对于nums中的数字2,其右边第一个比其大的值为3;
对于nums中的数字3,其右边不存在比其大的数,因此对应位置为-1;
2
3
4
5
6
7
8
解法一:暴力解
首先思考暴力解,对于数组中每个元素nums[i],需要向右遍历剩下的序列,找到第一个比该元素大的数,考虑最坏情况,对于[1,1,1,...1],数组的元素中全为1,每次需要遍历剩下的所有元素。
复杂度分析
- 时间复杂度为O(N ^ 2);
- 空间复杂度为O(1)。
解法二:使用单调栈
考虑优化时间复杂度,我们使用单调递增栈,从右向左遍历,对于元素nums[i],
- 若当前栈为空,则该元素右边不存在比它大的数;
- 若栈顶元素大于元素nums[i],则我们找到右边第一个大于nums[i]的数,该数为栈顶元素;
- 若栈顶元素小于或等于nums[i],则出栈,直到栈空或者栈顶元素大于nums[i];出栈操作结束后,栈为空或者栈顶元素大于nums[i],此时我们也可以根据上述前两种情况得到答案。
class Solution {
public int[] nextGreaterElement(int[] nums) {
Deque<Integer> stack = new LinkedList<>();
int[] ans = new int[nums.length];
for(int i = nums.length - 1; i >= 0; i--){
// 若stack不为空且栈顶元素小于或等于nums[i]时,需要出栈找到比nums[i]大的元素
while(!stack.isEmpty() && stack.peek() <= nums[i]){
// 出栈一是为了保证将nums[i]加入栈后保持单调性,
// 二是这些被出栈的元素小于等于num是nums[i],对于nums[i-1]来说,其右边第一个大于
// 它的数就不可能是这些要出栈的元素(比nums[i]小或等于的数)。
stack.pop();
}
// 此时skack要么为空,要么栈顶元素大于nums[i]
ans[i] = stack.isEmpty() ? -1 : stack.peek();
// 加入栈中,栈依然保持单调性
stack.push(nums[i]);
}
return ans;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
复杂度分析
- 时间复杂度:由于数组中每个元素最多出栈一次,故时间复杂度为O(N);
- 空间复杂度:使用了栈作为额外空间,故空间复杂度为O(N)。
# 739. 每日温度 (opens new window)
根据每日 气温 列表,请重新生成一个列表,对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。
例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
这题和第一题很类似,只是栈中存储的元素有点变化,简单思考一下暴力解,和第一题一样,对于每一个元素temperatures[i],都要向后搜索大于该元素的数temperatures[j],它们之间的天数就为j - i,特别地,当j == temperatures.length时,索引i后的元素没有比它大的,这时候对应位置为0,暴力法的时间复杂度为O(N ^ 2); 我们使用单调栈来优化时间复杂度,对于找下一个更大的元素,我们依然使用递增单调栈,它的解题思路和第一题一样,但是输出的是两个数之间的距离,也就是它们索引之差,我们只需对上述代码小小改造一下,存入栈中的是对应元素的索引,而不是元素本身,
class Solution {
public int[] dailyTemperatures(int[] T) {
int n = T.length;
int[] ans = new int[n];
Deque<Integer> stack = new LinkedList<>();
for(int i = n - 1; i >= 0; i--){
// 注意取 T[stack.peek()] <= T[i]
while(!stack.isEmpty() && T[stack.peek()] <= T[i]){
stack.pop();
}
// 若栈为空,则返回0,否者返回栈顶元素与当前索引的差值,即天数
ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;
// 将当前索引入栈
stack.push(i);
}
return ans;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 42. 接雨水 (opens new window)
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6
解法一:暴力解法 对于每一个柱子,往左边找其递增序列中最高的柱子left_max,向右找其递增序列中最高的柱子right_max,索引为i的柱子上所能接的雨水就为
area = 1 * min(left_max,right_max) - height[i]
height[i]为对应柱子自身的高度
2
例如对于索引5处高为0的柱子,其left_max=2,right_max=3,height[5] = 0, area = 1 * min(2, 3) - 0 = 2;我们遍历整个数组,找到每个元素的左右边界,计算它们所接的雨水,时间复杂度为O(N ^ 2)。
对暴力法的改进,我们可以通过一次遍历计算出每一个元素的左边界,也就是其左边最高的柱体,在一次遍历计算每一个元素的右边界,也就是其右边最高的柱体,柱体i所能接的水就为Math.min(rightBound[i], leftBound[i]) - height[i]
,将每个柱体所能接的水累加起来即为答案。
class Solution {
public int trap(int[] height) {
int ans = 0;
int n = height.length;
int[] leftMax = new int[n];
int[] rightMax = new int[n];
int max = 0;
for(int i = 0; i < n; i++){
if(max > height[i]){
leftMax[i] = max;
}else{
// 左边界不存在,记为-1,说明该柱体不能够接到水
leftMax[i] = -1;
max = height[i];
}
}
// 从后往前遍历,找到每个元素右边最高的柱体
max = 0;
for(int i = n - 1; i >= 0; i--){
if(max > height[i]){
rightMax[i] = max;
}else{
rightMax[i] = -1;
max = height[i];
}
}
for(int i = 0; i < n; i++){
if(leftMax[i] != -1 && rightMax[i] != -1){
// 累计能够接到水的面积
ans += Math.min(rightMax[i], leftMax[i]) - height[i];
}
}
return ans;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
改进后的暴力法的时间复杂度为O(n),空间复杂度为O(n);
解法二:利用单调栈特性 这道题结合了上述的两题,稍稍有点复杂,但是有思路后相当简单。 该题的问题可以转化为对于数组中的每一个元素,我们要找到其两旁的边界,以此计算它所能接水的面积,回顾单调递增栈,栈中的元素从栈顶到栈底是递增的,当要新加入一个元素到栈时,如果当前元素小于栈顶元素,我们将其加入栈中,当该元素大于栈顶元素时,我们要进行出栈操作,关键的部分就在于此,此时出栈的元素比要加入栈的新元素要小,如果栈中有比刚出栈的元素大,那么这两个较大元素就是出栈元素的边界,也就是说对于每一个出栈元素来说,其右边界就是当前要加入的元素(该元素大于出栈元素),其左边界就是当前的栈顶元素(当前栈顶元素 <= 出栈元素),由于我们计算接水面积时需要用到宽度,我们将栈中存储的元素的值改为存储元素的索引,此时我们可以得到出栈元素所能接水的面积:
h = height[stack.pop()];
ans = (min(height[stack.peek()], height[i]) - h) * (i - stack.peek() - 1);
2
此题计算雨水面积与暴力解法有所不同,读者可以手动在纸上模拟解法二,体会两者的区别。
class Solution {
public int trap(int[] height) {
Deque<Integer> stack = new LinkedList<>();
int ans = 0;
for(int i = 0; i < height.length; i++){
while(!stack.isEmpty() && height[stack.peek()] < height[i]){
int h = height[stack.pop()];
if(stack.isEmpty())
break;
ans += (Math.min(height[stack.peek()], height[i]) - h) * (i - stack.peek() - 1);
}
stack.push(i);
}
return ans;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 84. 柱状图中最大的矩形 (opens new window)
对于每一个元素来说,其所能勾勒出的最大面积由其最近的左右边界所决定。
维护一个单调栈,栈顶元素是最大的,给数组前后加上两个哨兵,确保遍历数组结束时除了哨兵外所有的元素都能够出栈,对于每一个出栈元素来说,其右边界就是当前要加入的元素(该元素小于出栈元素),其左边界就是当前的栈顶元素(当前栈顶元素 <= 出栈元素),若当前栈顶元素等于出栈元素时,该出栈元素就没有勾勒出最大面积,但是总能被与它相同的栈内元素(该元素严格大于栈内更深的元素)所勾勒出来。
class Solution {
public int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new LinkedList<>();
int maxArea = 0;
int n = heights.length + 2;
int[] newheights = new int[n];
newheights[0] = 0;
for(int i = 0; i < heights.length; i++){
newheights[i+1] = heights[i];
}
newheights[n-1] = 0;
stack.push(0);
for(int i = 1; i < n; i++){
while(newheights[i] < newheights[stack.peek()]){
// 对于每一个出栈的元素来说,其右边界是元素i,左边界就是当前的栈顶元素
int h = newheights[stack.pop()];
maxArea = Math.max(maxArea, h * (i - stack.peek() - 1));
}
stack.push(i);
}
return maxArea;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
另一种比较容易理解的方法,先找到每个元素的左右的比它矮的柱体所在的下标,这个时候柱体i所勾勒出来的面积就是
rightBound[i] - leftBound[i] - 1) * heights[i]
,比较每个元素所能勾勒的面积得到答案。
class Solution {
public int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new LinkedList<>();
int maxArea = 0;
int n = heights.length;
int[] leftBound = new int[n];
int[] rightBound = new int[n];
for(int i = 0; i < n; i++){
// 栈顶元素对应的柱体高度比当前柱子高时,出栈
while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
stack.pop();
}
// 此时栈要么是空,要么栈顶元素对应的柱体高度比当前柱子矮
leftBound[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
stack = new LinkedList<>();
for(int i = n-1; i >= 0; i--){
while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
stack.pop();
}
rightBound[i] = stack.isEmpty() ? n : stack.peek();
stack.push(i);
}
for(int i = 0; i < n; i++){
maxArea = Math.max(maxArea, (rightBound[i] - leftBound[i] - 1) * heights[i]);
}
return maxArea;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
总结:单调栈旨在解决在线性时间复杂度内寻找一个序列中每个元素的边界问题。