leetcode做题笔记84柱状图最大的矩形

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

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

思路一：单调栈

1.  
   int largestRectangleArea(int* heights, int heightsSize){
2.  
   int top = -1;
3.  
   int area, i;
4.  
   int maxarea = 0;
5.  
   int *stack = (int *)malloc(sizeof(int) * (heightsSize 2));
6.  
   int *buff = (int *)malloc(sizeof(int) * (heightsSize 2));
7.  
    
8.  
   buff[0] = 0;
9.  
   for (int i = 1; i <= heightsSize; i ) {
10.  
    buff[i] = heights[i - 1];
11.  
    }
12.  
    buff[heightsSize 1] = 0;
13.  
     
14.  
    stack[ top] = 0;
15.  
    for (i = 1; i < heightsSize 2; i ) {
16.  
    while (top > 0 && buff[i] < buff[stack[top]]) {
17.  
    area = (i - stack[top - 1] - 1) * buff[stack[top]];
18.  
    maxarea = maxarea > area ? maxarea : area;
19.  
    top--;
20.  
    }
21.  
    stack[ top] = i;
22.  
    }
23.  
    return maxarea;
24.  
    }

分析：

本题利用单调栈的特性，有两种做法，一是直接从中间数向左右进行递归，判断是否单调递增或递减计算答案，第二种是多加一个空间，从最左边或最右边判断是否为单调递增或递减，此做法多设置了一个空间，利用单调栈向左单调递减的特性找最小值计算矩形的最大值，最后输出答案。

总结：

本题考察单调栈相关知识，利用单调递减递归找到最小值计算矩形大小，最后返回最大值

这篇好文章是转载于：学新通技术网