首页 > 代码库 > [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 直方图中最大的矩形