首页 > 代码库 > [Leetcode] largest rectangle in histogram 直方图中最大的矩形

[Leetcode] largest rectangle in histogram 直方图中最大的矩形

Given n non-negative integers representing the histogram‘s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

技术分享

Above is a histogram where width of each bar is 1, given height =[2,1,5,6,2,3].

 

技术分享

The largest rectangle is shown in the shaded area, which has area =10unit.

 

For example,
Given height =[2,1,5,6,2,3],
return10.

题意:求直方图中最大的矩形面积

思路:比较直接的方式是,遍历数组,计算以每个值为起点的最大面积,取其最大值,如题中例子,值得注意的是,以2为起点,遍历到5时,应该是1*3=3,即取最小值相乘。但其时间复杂度为O(n^2)。于是上网找到了实验室小纸贴校外版的博客,其给出了时间复杂度为O(n)的算法。其主要的思想是:用一个栈来保存下标(索引),遇到比栈中下标对应的值大的高度时,就将这个这个高度的下标压入栈中,即保证栈中下标对应的高度是非降型的;遇到比栈中下标对应值小的高度,就计算此时的面积,和res比较,取较大值。为了保证到最后时依旧存在一个不升状态,即结束状态,要在height中压入一个0。下面结合自己的想法给出详细的说明。

以题中例子:height =[2,1,5,6,2,3],

1) 刚开始栈中为空,压入下标0;然后当i=1时,2<=1不成立,下标出栈,栈变为空,计算此时面积res=2;

技术分享

 

 2)高度1,5,6是依次递增的,所以对应下标依次压入栈中;当i=4时,6>2,下标3出栈,所以计算此时的面积res=6,如图:

技术分享

3)栈顶元素为2,其对应的高度为5>2(此时,还要和下标i=4的高度比较),所以,栈顶元素2出栈,计算面积为res=10;

技术分享

 4)因为栈顶元素为1,其对应的高度为1<2,满足条件,所以,将i入栈,直到i=6(为压入的0此时栈中的元素为{1,4,5},有一个栈顶元素对应的高度大于i=6对应的高度,所以,5出栈,计算面积为3,其中最大面积为10;

 技术分享

5)栈顶元素为2,其对应高度为2>0,所以,2出栈,计算面积为4,最大面积为10;

技术分享

6) 此时,栈顶元素为1,对应高度为1>0,所以,1出栈,因为1出栈以后,栈变为空,所以,计算面积的方式有变化,res=height[1]*6=6,最大面积为10。

技术分享

 代码如下:

 1 class Solution {
 2 public:
 3     int largestRectangleArea(vector<int> &height) 
 4     {
 5         int res=0;
 6         stack<int> stk;
 7         height.push_back(0);
 8         for(int i=0;i<height.size();++i)
 9         {
10             if(stk.empty()||height[stk.top()]<=height[i])
11                 stk.push(i);
12             else
13             {
14                 int temp=stk.top();
15                 stk.pop();
16                 res=max(res,height[temp]*(stk.empty()?i:(i-stk.top()-1)));
17                 --i;
18             }
19         }
20         return res;    
21     }
22 };

 总结:主要的思想是用栈维护一个高度非降型的下标,若是有降,则计算面积,直到重新回到非降型。所以,为维护到最后时,能计算面积的情况,需在最后加入0

[Leetcode] largest rectangle in histogram 直方图中最大的矩形