@ 代码随想录算法训练营第9周（C语言）|Day64（单调栈）

@ 代码随想录算法训练营第9周（C语言）|Day64（单调栈）

Day64、单调栈（包含题目 84.柱状图中最大的矩形 ）

84.柱状图中最大的矩形

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

题目解答

int largestRectangleArea(int* heights, int heightsSize) {
    int heights1[heightsSize+2];
    heights1[0]=0;
    heights1[heightsSize+1]=0;
    for(int i=1;i<heightsSize+1;i++){
        heights1[i]=heights[i-1];
    }
    int res=0;
    int stack[heightsSize+2];
    int stacktop=0;
    memset(stack,0,sizeof(stack));
    stack[stacktop++]=0;
    for(int i=1;i<heightsSize+2;i++){
        if(heights1[i]<heights1[stack[stacktop-1]]){
            while(stacktop!=0&&heights1[i]<heights1[stack[stacktop-1]]){
                int mid=stack[stacktop-1];
                if(stacktop!=0){
                    stacktop--;
                    int left=stack[stacktop-1];
                    res=fmax(res,(i-left-1)*heights1[mid]);
                }
            }
        }
        stack[stacktop++]=i;
    }
    return res;
}
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

题目总结

找到最大的值heights1[stack[stacktop-1]]然后计算长宽计算最大的矩形。