[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 = 10 unit.

Example:

Input: [2,1,5,6,2,3] Output: 10

 

题意：

给定一个直方图，求其能覆盖的最大矩形。

 

思路：

以下是O(n²) 的时间复杂度解法

 当 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

相关资源：数据结构—成绩单生成器