单调栈

Posted on   |   In   |  

单调栈的应用

单调栈

以前自己对栈的认识紧限于陷入后出的数据结构，实现一个逆序输出。直至遇到了这道题目，让我对栈有了重新的认识。

单调栈的原理

题目如下：
给出一个柱形统计图(histogram),它的每个bar的宽度为1，现在需求出柱形图中所能组成的矩形的最大面积。例如:6 2 1 5 6 2 3 ,其中7代表统计图中的bar的个数，后面的数据分别表示每个bar的高度。

histogram

先说一下自己难道题目的第一反应，分别计算出每个高度可以向左和向右扩展的长度，然后计算出每个高度对应的矩形的面积，得到最大值。显然这是一个$O(n^2)$复杂度的算法。

那么有没有更简单的算法了：当然有，单调栈
先介绍以下单调栈的执行过程：
从第一个bar开始往后扫描，扫描过程满足以下规则
(1)如果全部元素入栈，则将栈弹空；
(2)如果当前的bar的高度大于栈顶bar的高度，则将当前bar的下标入栈；
(3)否则执行出栈操作，直到栈顶的元素小于当前要入栈的元素，记录弹出下标对应的bar的高度，并计算出一个面积，比较这个面积与当前的最大面积，最后得到最大面积。

栈中的保存的元素为(高度，起始的索引号)
算法的执行过程为：

  1. 初始化时，栈底的元素为(0,0)，i = 1,面积s = 0,上一次的高度lastHeight = 0；
  2. 此时 i = 1,加入第一个元素(2,1),满足条件(1)，故入栈，栈中的元素为(0,0),(2,1);
  3. i=2 ,加入第二个元素(1,2)，满足条件(2),将要出栈，$面积 = (i-startindex)height$，计算出的面积为 s = 2,lastHeight = 2 > 1,将(1,1)入栈，*栈中的元素为(0,0), (1,1);
  4. i = 3 (5,3),入栈栈中的元素为(0,0), (1,1),(5,3);
  5. i = 4 (6,4),入栈栈中的元素为(0,0), (1,1),(5,3),(6,4);
  6. i = 5 (2,5),出栈，(6,4)出栈计算面积$s_1 = (5-4)6 = 6$,(5,3)出栈$s_1 = (5-3)5 = 10$,到(1,1)时， 1 < 2,故将(2,3)入栈，此时的元素为(0,0),(1,1),(2,3);
  7. i = 6, (3,6),入栈，此时全部入栈，将栈弹空；

单调栈的实现

具体实现的代码为：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#define length 9
struct ele{
	int height;
	int startIndex;
};
typedef struct ele node;
int main()
{
	node stack[length];
	int top = 0;   //top记录下一个位置
	int index = 0;  //遍历数组
	int height[length] = {8, 3, 6, 2, 4, 5, 6, 1, 2};//第一个元素代表数组的长度
	int max_rect = 0;
	int rect;
	stack[0].height = 0;
	stack[0].startIndex = 1;
	top++;
	for (index = 1; index <= height[0]; index++){
	    /*栈顶元素小于即将入栈的高度*/
		if (height[index] >= stack[top - 1].height){
			stack[top].height = height[index];
			stack[top].startIndex = index;
			top++;
		}else{
			while(stack[top - 1].height > height[index] && top > 1){
				rect = (index - (stack[top - 1].startIndex))*(stack[top - 1].height);
				if (rect > max_rect)
					max_rect = rect;
				top--;
			}
			/*将新的高度入栈，此时栈顶的元素高度<=当前高度，所以此时的新的高度的startIndex = 刚出栈元素的startIndex*/
			//stack[top].startIndex = stack[top -1].startIndex;
			stack[top].height = height[index];
			top++;
		}
	}
	if (top > 0){
		while(stack[top - 1].height > height[index] && top > 1){
			rect = (index - (stack[top - 1].startIndex))*(stack[top - 1].height);
			if (rect > max_rect)
				max_rect = rect;
			top--;
		}
	}
	printf("the largest rect is %d.\n",max_rect);
	return 0;
}

leetcode Largest Rectangle in Histogram

代码如下：

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
33
34
35
36
37
38
39
int largestRectangleArea(int* height, int heightSize){
	typedef struct ele{
	int heig;
        int startIndex;
    	}node;
    	node stack[heightSize+1];
    	int top = 0;
    	stack[0].heig = 0;
    	stack[0].startIndex = 0;
    	top++;
    	int index,rect;
    	int max_rect = 0;
    	for (index = 0; index < heightSize; index++){
        	if(height[index] >= stack[top -1].heig){
            	stack[top].heig = height[index];
            	stack[top].startIndex = index;
            	top++;
        	}else{
        		while(height[index] < stack[top -1].heig && top > 0){
                		rect = (index -stack[top-1].startIndex) * stack[top -1].heig;
                		top--;
                		if (rect > max_rect)
                    			max_rect = rect;
            		}	
            		//int start = stack[top].startIndex;
            		//stack[top].startIndex = start;
			/*此处的startIndex是刚弹出的元素的startIndex，只需要改变heig*/
            		stack[top].heig = height[index];
            		top++;
        	}
    	}
    	while(top > 0){
        	rect = (index -stack[top-1].startIndex) * stack[top -1].heig;
        	top--;
        	if (rect > max_rect)
            		max_rect = rect;
    	}
    	return max_rect;
}