@ 代码随想录算法训练营第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
        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
        if(heights1[i]
            while(stacktop!=0&&heights1[i]
                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;
}