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 = . The largest rectangle is shown in the shaded area, which has area = unit. Example: | 給定 n 個非負整數,用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰,且寬度為 1 。 求在該柱狀圖中,能夠勾勒出來的矩形的最大面積。 以上是柱狀圖的示例,其中每個柱子的寬度為 1,給定的高度為 [2,1,5,6,2,3]。圖中陰影部分為所能勾勒出的最大矩形面積,其面積為 10 個機關。 示例: 輸入: [2,1,5,6,2,3] 輸出: 10 |
思路:從前往後每選到一個局部峰值(目前高度小于下一個高度,比如圖中2,6,3),然後從目前位置往前找最大矩形。也就是找到目前最小高度x寬。
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int res=0;
for(int i=0;i<heights.size();++i)
{
if(i+1<heights.size() && heights[i]<=heights[i+1]) //一定要先判斷i在範圍内
continue;
int mn=heights[i];
for(int j=i;j>=0;j--)
{
mn=min(mn,heights[j]);
res=max(res,mn*(i-j+1));
}
}
return res;
}
};