栈和队列的应用

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
49
50
#include <stdio.h>
#define SIZE 100
#define length 9
struct ele{
	int height;
	int startIndex;
};
typedef struct ele node;
int main()
{
	node stack[SIZE];
	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;
}

单调队列

sliding window maximun

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
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100000

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){

    int deq[MAX_N];
    int *ret = (int *)malloc(sizeof(int) * (numsSize -k + 1));
    int s =0,  t = 0;
    int i;

    for(i = 0; i < numsSize; ++i){
        /*
         *判断当前队列是否有多余的值，即队首的元素可能
         *不在(i-k+1, i)这个窗口内
         */
        if (s < t && i - k == deq[s])
                s++;
        /*当前要进队的元素，队尾的元素比它小，则出队*/
        while(s < t && nums[deq[t-1]] < nums[i])
            t--;
        deq[t++] = i;

        if (i >= k-1){
            *(ret + i- k + 1) = nums[deq[s]];
        }
    }
    *returnSize = numsSize- k + 1;
    return ret;
}

int main(){
    int a[]={1,3,5,4,2};
    int ret;
    int *out = maxSlidingWindow(a, sizeof(a)/sizeof(int), 3, &ret);
    int i;
    for(i= 0; i < ret; i++){
        printf("%d ", *(out+i));
    }
    free(out);
    return 0;
}