栈和队列的应用

最近在做题目的时候,发现了一种很好的数据结构:单调栈单调队列


栈和队列的应用

单调栈

以前自己对栈的认识紧限于陷入后出的数据结构,实现一个逆序输出。直至遇到了这道题目,让我对栈有了重新的认识。
题目如下:
给出一个柱形统计图(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;
}