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 =
10
unit.
Example:
Input: [2,1,5,6,2,3]
Output: 10 題意：
給定一個直方圖，求其能覆寫的最大矩形。
思路：
以下是O(n2) 的時間複雜度解法
當 i= 0 1 2 3 4
area= 2*1 4*1 6*1 5*1 3*1
2*2 4*2 5*2 3*2
2*3 4*3 3*3
2*4 3*4
2*5
以height[i]為臨界，每次比較其左側的所有height誰更小，更新minHeight, 更新目前maxArea
1 class Solution {
2 public int largestRectangleArea(int[] heights) {
3 int maxArea = 0;
4 for(int i = 0; i < heights.length; i++){
5 int minHeight = heights[i]; //以height[i]為臨界
6 for(int j = i; j >= 0; j--){ // 每次比較其左側的所有height誰更小
7 minHeight = Math.min(minHeight, heights[j]);
8 maxArea = Math.max(maxArea, minHeight * (i - j + 1));
9 }
10 }
11 return maxArea;
12 }
13 } 以下是O(n) 的時間複雜度解法
維護一個單調棧monoStack，數組中每個元素的index都入棧、出棧
代碼：
1 class Solution {
2 public int largestRectangleArea(int[] heights) {
3 Stack<Integer> s = new Stack<>();
4 int area = 0;
5 for(int i=0; i<= heights.length;){
6 int value = i< heights.length ? heights[i]: 0;
7 if(s.isEmpty() || value> heights[s.peek()]){
8 s.push(i);
9 i++;
10 }else{
11 int temp = s.pop();
12 area = Math.max(area, heights[temp] * (s.isEmpty() ? i: (i-s.peek()-1)));
13 }
14
15
16 }
17 return area;
18 }
19 } 轉載于:https://www.cnblogs.com/liuliu5151/p/9207365.html