单调栈
栈的概念大家都是清晰的， 就是维系一个先进后出，后进先出的容器。
那么单调栈， 显而易见， 就是要维护我们的栈是单调的，也就是递增的或者递减的。
以上就是单调栈的全部描述。
这绝对是没有营养的解释，但是实际上单调栈的内容就是这么多。所以我们通过一些例子来进一步解释看这个单调栈的运用。
单调栈的模板
我们要维持一个栈是单调的，要么是单调升，要么是单调减的。那么我们在栈里面存放的是什么数据呢？一般而言是数据的索引，而非具体的值。
- 首先创建一个单调栈用来存放索引。
- 遍历数组，从单调栈里取索引数据，看是否满足条件（比如说对于单调递减栈，如果索引对应的数据 < 当前数据，则表示当前数据比top数据大，不能再入栈了，需要处理了）
- 当需要处理时，将栈内的元素一次出栈，然后进行处理，直到栈顶元素不再满足条件
- 将当前元素入栈
1 | vector<int> dailyTemperatures(vector<int>& temperatures) { |
leetcode上的实例
这道题实际上就是求比当前数更大的数的位置。那么我们需要维持一个单调递减的栈，当将要入栈的元素大于栈顶的元素时，栈顶元素出栈，我们就计算这两个数的索引的差值。
需要注意的是栈里存放的是元素的索引，而不是元素的值，这一点是需要注意的。
1 | int* dailyTemperatures(int* T, int TSize, int* returnSize){ |
这个题目跟739是一样的问题。只不过这里的描述改为了股票跨度问题罢了。1
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// 维护一个单调递减栈
// 还有一个index存放比num[i]小的天数
typedef struct {
int index[10001];
int monoStack[10001];
int head;
} StockSpanner;
StockSpanner* stockSpannerCreate() {
StockSpanner* stock = (StockSpanner*)malloc(sizeof(StockSpanner));
stock->head = -1;
return stock;
}
int stockSpannerNext(StockSpanner* obj, int price) {
int i=1;
while(obj->head != -1 && obj->monoStack[obj->head] <= price){
i += obj->index[obj->head];
(obj->head)--;
}
obj->monoStack[++(obj->head)] = price;
obj->index[(obj->head)] = i;
return i;
}
void stockSpannerFree(StockSpanner* obj) {
free(obj);
}
这个题目稍微有一点难度了，这个不再是在一个数组中比较，而是在两个数组中比较了，然而实际上这个也不难，实际上我们只需要求得nums2中的每个元素的下一个最大值即可，而num1是num2的子集，所以我们只需要做下hash映射，就可以得到 nums1 中每个元素在 nums2 中的下一个比其大的值。
所以我们需要维持一个单调递减栈， 然后维持一个数组，用来存放当前元素的下一个最大元素。
1 | int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){ |
这个题目看起来是很简单的，就是单调栈的经典模型，求下一个的最大元素罢了，唯一有一点改变的就是对于后面的元素，要循环遍历，而不是直接终止。
那么一个解决方案就是对后面的找不到最大值得元素，再进行一遍遍历。
实际上我们可以将数组复制一遍，变为原来的数组的两倍大小，然后进行单调栈遍历。这也是处理循环问题的标准套路。1
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
30int* nextGreaterElements(int* nums, int numsSize, int* returnSize){
*returnSize = numsSize;
if(numsSize==0) return NULL;
int* numTmp = (int*)malloc(2*numsSize*sizeof(int));
for(int i=0; i<numsSize; i++){
numTmp[i] = nums[i];
}
for(int i=numsSize; i<2*numsSize; i++){
numTmp[i] = nums[i - numsSize];
}
int* result = (int*)malloc(2*numsSize*sizeof(int));
int* monoStack = (int*)malloc(2*numsSize*sizeof(int));
int head = -1;
for(int i=0; i<2*numsSize; i++){
result[i] = -1;
while(head != -1 && numTmp[monoStack[head]] < numTmp[i]){
result[monoStack[head]] = numTmp[i];
head--;
}
monoStack[++head] = i;
}
free(monoStack);
free(numTmp);
return result;
}
这道题就有点难度了，不是直观的用单调栈可以直接看出来的了。下面我们分析一下，要求最大的矩形的面积，那么矩形的面积由宽和高决定。高是确定的，那么我们就可以很容易的确定以当前高度为高的矩形的面积，这只要向左右两边扩散，找到边界点即可（所谓的边界点的高度一定是小于当前的矩形的高度的）。我们看一下暴力解法的操作1
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
33int largestRectangleArea(int* heights, int heightsSize){
if(heightsSize==0) return 0;
int* newHeights = (int*)malloc((heightsSize+1)*sizeof(int));
for(int i=0; i<heightsSize; i++) {
newHeights[i] = heights[i];
}
newHeights[heightsSize] = 0;
int result = heights[0];
for(int i=0; i<heightsSize; i++){
int left = -1;
int right = heightsSize;
for(int j=i-1; j>=0; j--){
if(newHeights[j] < newHeights[i]){
left = j;
break;
}
}
for(int j=i+1; j<heightsSize+1; j++){
if(newHeights[j] < newHeights[i]){
right = j;
break;
}
}
result = fmax(result, (right-left-1)*newHeights[i]);
}
free(newHeights);
return result;
}
暴力解法有个问题啊，那就是他的时间复杂度有点高o(n^2), 而且我们可以看出来暴力解法中存在着大量的重复计算，我们无法利用已经计算过的结果。
我们以例子中的数组为例[2,1,5,6,2,3]
以2为高度的矩形，我们继续向后遍历，下一个值为1， 那么以2为高度的矩形的面积就可以确定了。然后1为高度的矩形，我们向后遍历，下一个值为5，确定不了。我们先不管他，继续向后遍历，以5为高度的矩形，我们还是确定不了它的面积，继续向后遍历，以6为高度的矩形，我们可以确定他的面积大小了（因为他的下一个值比他小）。然后我们可以确定5了，但是1还是确定不了，所以我们要继续向下遍历，找到1的边界。
因此我们可以总结一下，这就是一个单调递增的栈，栈里面存放的元素就是我们暂时还无法确定其右边界的元素啊。
1 | /* |
这道题目是上面题目的变形，实际上如果我们的想法是看两个柱子之间能容纳多少水的话，这个题目就有点复杂了。如果我们换个思路，我们题也可以这样考虑，我们只要计算每个柱子上能容纳多少水就可以了。如图所示，第一个柱子上没水，第二个柱子上没水，第三个柱子上1个水，第四个柱子上没水……， 那么这个题目就比较清晰了。这个问题实际上还是需要确定当前高度的左右边界问题，跟上面的问题的思想是一样的。
这个有个比较清晰的图示1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24//如果当前元素小于栈顶元素，则把当前元素的索引入栈，如果当前元素大于栈顶元素，则说明栈顶元素对应的值肯定是在当前元素和其下面元素之间。那么我么您就可以计算得到这一部分的雨水量。
int trap(int* height, int heightSize){
if(heightSize == 0) return 0;
int ans = 0;
int stack[heightSize];
int head = -1;
int current = 0;
while(current <heightSize) {
while(head != -1 && height[current] >height[stack[head]]) {
int top = stack[head];
head--;
if(head == -1){
break;
}
int distance = current - stack[head] - 1;
int value = fmin(height[stack[head]], height[current]) - height[top];
ans += value*distance;
}
stack[++head] = current++;
}
return ans;
}
实际上这道题还有不这么烧脑的解法，就是我们对于每个点，用动态规划的方法，提前算出来他的左右边界就好了，很简单吧。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19int trap(int* height, int heightSize){
if(heightSize == 0) return 0;
int leftMax[heightSize];
int RightMax[heightSize];
leftMax[0] = height[0];
for(int i=1; i<heightSize; i++) {
leftMax[i] = fmax(leftMax[i-1], height[i]);
}
RightMax[heightSize-1] = height[heightSize-1];
for(int i = heightSize-2; i>=0; i--) {
RightMax[i] = fmax(RightMax[i+1], height[i]);
}
int ans = 0;
for(int i=1; i<heightSize-1; i++) {
ans += fmin(leftMax[i], RightMax[i]) - height[i];
}
return ans;
}
多余的话
实际上遇到问题的话，最容易想到的就是暴力解法。暴力解法重来都不是什么问题，所谓的解题思路都是从暴力解法开始的，因为暴力解法存在着各种各样的重复计算，所以才使人们不断的想出新的算法，以空间换时间或者其他的方式，来优化解决方案。
写在最后的话
实际上单调栈分析简单的问题是很容易想到的，但是分析后两个这种有难度的问题还是比较烧脑的，也是比较难想到的。实际上很多类似的问题可以用动态规划来解决，这个难度就降了不少了。