文章目录
初识单调栈问题
引例
例题:
给定一个数组，输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数。如果不存在，则输出 -1。
输入: [1,2,1]
输出: [2,-1,-1]
首先我们来看上面这道问题。最容易想到的思路是遍历数组，对于每一个元素，从该元素起向后遍历，寻找比它大的数。伪代码如下：
//例题的暴力解法
int[] res = new int[nums.length];//res是结果数组，nums是传入数组。
for(int i = 0;i<nums.length;i++){
for(int j = i;j < nums.length;j++){
if(nums[j] > nums[i]){
res[i] = nums[j];
continue;
}
nums[i] = -1;
}
}
显然，算法的时间复杂度是O(n²)。那么有没有时间复杂度更低的算法呢？答案是有的，这就是利用单调栈解题的方法。
栈与单调栈
栈是一种后进先出的数据结构，广泛运用于计算机的各个角落，想必大家都已经非常熟悉了。而单调栈是指栈中的元素单调递增或单调递减的栈。例如将5，4，3，2，1依次压入栈stack中，stack就是一个单调递减的栈。利用单调栈中元素递增或递减的性质，可以解决许多问题。
例如上面的例题，我们观察可以知道：数组元素递减的时候，不影响对应结果。我们构造一个栈来存放数组下标。遍历数组，对于每一个元素：当栈为空或当前元素小于下标为栈顶数字的数组元素时，把当前元素的下标push到栈中；当当前元素大于下标为栈顶元素的数组元素时，将栈顶元素取出，将结果数组中下标为栈顶元素的位置设为原数组的当前元素，并重复上述操作，直到当前元素小于下标为栈顶元素的数组元素。遍历完成，也就得到了结果数组。这样以来算法的时间复杂度降低为O(n)。在这个过程中，我们构造的栈中存放的下标对应的数组元素是递减的。因此这种解法可以算作一种单调栈解法。也就是说：
- 一般来说，单调栈解法中的栈存放的往往是元素下标，而不是元素本身，因此单调指栈中元素对应的数组元素是单调递增或递减的。栈中元素的递增或递减只取决于从左到右还是从右到左遍历数组。
//例题的单调栈解法
Stack<Integer> stack = new Stack<>();
int[] res = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
res[i] = -1;
if (!stack.empty() && nums[i] > nums[stack.peek()]) {
while (!stack.empty() && nums[i] > nums[stack.peek()]) {
res[stack.pop()] = nums[i];
}
}
stack.push(i);
}
return res;
完整例题
实际上，例题是LeetCode中第503题的简化版本。下面是原题：
LeetCode.503:
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
输入: [1,2,1]
输出: [2,-1,2]
多了一个循环的条件，但是解题思路没有很大变化，在第一次遍历到数组结尾后，再进行一次遍历即可。
//LeetCode.503解法
public int[] nextGreaterElements(int[] nums) {
Stack<Integer> stack = new Stack<>();
int[] res = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
res[i] = -1;
if (!stack.empty() && nums[i] > nums[stack.peek()]) {
while (!stack.empty() && nums[i] > nums[stack.peek()]) {
res[stack.pop()] = nums[i];
}
}
stack.push(i);
}
if (stack.empty()) return res;
for (int num : nums) {
if (!stack.empty() && num > nums[stack.peek()]) {
while (!stack.empty() && num > nums[stack.peek()]) {
res[stack.pop()] = num;
}
}
}
return res;
}
进阶：单调栈解法的共性
新的问题
例题中，单调栈解法降低了解题算法的时间复杂度。但是，仅仅掌握这一道题的做法显然是不够的，我们应该追问，为什么单调栈解法可以降低时间复杂度，在什么情况下我们应该考虑使用单调栈解法呢？
我们再来看一道类似的题目：
LeetCode.739:
根据每日气温列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],
你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
这道题与例题非常像，无非是结果数组记录的内容从第一个更大数，变成了第一个更大数字与当前数字之间的距离。直接上解法：
public int[] dailyTemperatures(int[] T) {
if (T.length == 0) return new int[0];
Stack<Integer> stack = new Stack<>();
int[] res = new int[T.length];
for (int i = 0; i < T.length; i++) {
if (!stack.empty() && T[stack.peek()] <= T[i]) {
while (!stack.empty() && T[stack.peek()] <= T[i]) {
res[stack.peek()] = i - stack.pop();
}
}
stack.push(i);
}
return res;
}
这两道题目有一个共同的特点，当数组元素递减的时候，它们对应的结果是相同的。
然后是一道稍微难一点的题目：
LeetCode.42:
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
3 #
2 # @ @ @ # # @ #
1 # @ # # @ # # # # # #
0 1 2 3 4 5 6 7 8 9 10 11 12
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，#代表柱子，@代表雨水。在这种情况下，可以接 6 个单位的雨水。
这道题结合了生活实际。我们观察可以知道，如果柱子高度递减，显然是无法储水的；只有在柱子高度递减后再增高，才有了储水的空间。那么，我们根据例题的方式，构建一个递减栈，存储柱子的下标，当柱子高度高于之前的柱子时，计算以当前柱子为右侧边界的储水面积。这样将一块不规则的储水面积划分为几个矩形，例如题例中第二部分T形的储水部分，第7根柱子比第6根高，所以计算第7根柱子为右界的储水面积为1；遍历到第8根柱子时，坐标为(6,0)的部分已经计算过,因此计算4，8根柱子之间上方矩形的面积即可。
这是我接触到的第一道单调栈问题，自己的解法比较繁琐，因此在此给出LeetCode官方题解：
//42题官方题解
int trap(vector<int>& height)
{
int ans = 0, current = 0;
stack<int> st;
while (current < height.size()) {
while (!st.empty() && height[current] > height[st.top()]) {
int top = st.top();
st.pop();
if (st.empty())
break;
int distance = current - st.top() - 1;
int bounded_height = min(height[current], height[st.top()]) - height[top];
ans += distance * bounded_height;
}
st.push(current++);
}
return ans;
}
回过头来看题例，已经知道底部柱子高度的情况下，每一个储水的矩形块的储水面积是由什么决定的呢？是该矩形块左右两侧第一个高度大于该矩形块底柱子高度的柱子的位置和高度。这样说比较拗口，我们直接看题目下的例子，第一个能储水的矩形块底高为0左右双方第一个比底高高的柱子分别是第2根和第4根，距离为1，高度分别为1，2；第二个矩形块底为0，双方柱子是第5，7根柱子，距离为1，高度为1，1；第三个矩形块底高为1，左右是第4、8根柱子，距离为3，高度为2，3 。第四个矩形块以此类推。仔细想想，本段标黑的内容跟本文的第一个例题所求的结果是不是有些类似呢？事实上，在本题中单调栈的应用正是这一部分内容的求解。而且已知当前元素与下一元素的差值，数组元素单调递减时，不会影响对应矩形的面积。这个说法不太准确，我举个例子来说：[10,8,7,6,5,4,3,10]和[10,8,0,0,0,0,0,10]，10和8确定后，后面的元素是7,6,5,4,3还是0,0,0,0,0不影响8-10这一层的矩形面积。
我们继续看下一题。
LeetCode.84:
给定n个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
例如： [2,1,5,6,2,3]
7 6
6 5 #
5 # #
4 # # 3
3 2 # # 2 #
2 # 1 # # # #
1 # # # # # #
0 1 2 3 4 5 6 7
最大面积就是 5*2 = 10;
这道题跟接雨水的问题看起来有些相似。我们这次构造一个递增的单调栈（再次提醒，单调的是数字元素，栈中的是元素下标）。遍历数组，当当前数组元素比下标为栈顶元素的数组元素大，直接将下标压入栈中；否则取出栈顶元素，计算以高度为以该元素为下标的数组元素的矩形的最大面积，重复以上操作直到栈顶元素对应数组元素小于数组当前元素，将数组当前下标压入栈。这里比较拗口，举个例子，遍历到题例中的2时，取出6，计算面积为6*1，然后取出5，计算面积为5*2。此时栈顶元素为1，将2压入栈中，继续遍历数组。数组遍历结束，栈中还有元素，也要分别计算面积。最后比较得出最大值。读代码比听我白话清晰：
//84题解法
public int monotonousStack(int[] heights) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int maxarea = 0;
for (int i = 0; i < heights.length; ++i) {
while (stack.peek() != -1 && heights[stack.peek()] >= heights[i])
maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
stack.push(i);
}
while (stack.peek() != -1)
maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() - 1));
return maxarea;
}
第二个while循环是考虑栈中剩余元素的情况，在stack中预先加入一个-1，是为了处理所有柱子中高度最低的柱子，此时矩形的宽是整个柱状图的宽。这里的处理参考了LeetCode官方题解。
归纳与总结
从以上的例题中，我们不难发现一个共性，就是当数组元素的增减性为递增或递减时不会影响结果，而不是该增减性时会对结果立刻产生影响的问题，往往可以引入单调栈进行解决。例如第一个例题中，递减不产生影响，而增加时立刻产生影响。这样，递减时没有影响，递增时可以立刻得到影响的结果，只需要讨论增减性发生变化的点。单调栈解法降低时间复杂度的方法也正是如此：从要对每个元素进行讨论简化为对增减性发生变化的点进行讨论后，通过栈中存储的下标，高效地找到比当前元素大（小）的元素。
再进阶：变形的单调栈问题
我们已经讨论过典型的单调栈问题，再看下面一题：
LeetCode.85
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
例如输入:
["1","0","1","0","0"], # #
["1","0","1","1","1"], # # # #
["1","1","1","1","1"], # # # # #
["1","0","0","1","0"] # #
这道题不能直接套用单调栈的做法。但是可以将整个图按行转换成5个柱状图，从而转化为上述的第84题分别求解，再取最大值。
分别为每一行为底，构造柱状图。
例如题例中，可以构造：(@用来占位，实际该处为空)
1. 2. 3. 4.
1 #
2 # # # #
3 # # # # # # # #
4 # @ # @ @ # @ # # # # # # # # # @ @ # @
代码如下：
//85题解法
public int monotonousStack(char[][] matrix) {
if (matrix.length == 0) return 0;
int[] heights = new int[matrix[0].length + 1];
int maxArea = 0;
for (char[] chars : matrix) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int col = 0; col <= matrix[0].length; col++) {
if (col < matrix[0].length) {
if (chars[col] == '1')
heights[col] += 1;
else heights[col] = 0;
}
if (stack.peek() != -1 && heights[stack.peek()] > heights[col]) {
while (stack.peek() != -1 && heights[stack.peek()] > heights[col]) {
maxArea = Math.max(maxArea, heights[stack.pop()] * (col - stack.peek() - 1));
}
}
stack.push(col);
}
}
return maxArea;
}
参考
LeetCode https://leetcode-cn.com/ 第42、84、85、503、739题及题解