首页 > 代码库 > 【LeetCode】84. Largest Rectangle in Histogram——直方图最大面积

【LeetCode】84. 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.

 

思路:

1、如果已知height数组是升序的,应该怎么做?

比如1,2,5,7,8

那么就是(1*5) vs. (2*4) vs. (5*3) vs. (7*2) vs. (8*1)

也就是max(height[i]*(size-i))

2、使用栈的目的就是构造这样的升序序列,按照以上方法求解。

但是height本身不一定是升序的,应该怎样构建栈?

比如2,1,5,6,2,3

(1)2进栈。s={2}, result = 0

(2)1比2小,不满足升序条件,因此将2弹出,并记录当前结果为2*1=2。

将2替换为1重新进栈。s={1,1}, result = 2

(3)5比1大,满足升序条件,进栈。s={1,1,5},result = 2

(4)6比5大,满足升序条件,进栈。s={1,1,5,6},result = 2

(5)2比6小,不满足升序条件,因此将6弹出,并记录当前结果为6*1=6。s={1,1,5},result = 6

2比5小,不满足升序条件,因此将5弹出,并记录当前结果为5*2=10(因为已经弹出的5,6是升序的)。s={1,1},result = 10

2比1大,将弹出的5,6替换为2重新进栈。s={1,1,2,2,2},result = 10

(6)3比2大,满足升序条件,进栈。s={1,1,2,2,2,3},result = 10

栈构建完成,满足升序条件,因此按照升序处理办法得到上述的max(height[i]*(size-i))=max{3*1, 2*2, 2*3, 2*4, 1*5, 1*6}=8<10

综上所述,result=10

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

 

【LeetCode】84. Largest Rectangle in Histogram——直方图最大面积