[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

柱状图中最大的矩形。

题意是给一个数组表示一些非负整数，代表一些bars，请你返回由这些bar组成的最大矩形的面积。

思路是单调栈。这个题可以用别的方法，但是复杂度都不如单调栈的思路。关于这个题本身，我参考了这个帖子，他讲的非常好，起码帮助我理解了这道题单调栈的做法。至于代码，你只要看懂这个帖子的讲解，代码一定看得懂。唯一需要注意的是为什么for loop要遍历到input结束之后再多一步，是为了让遍历完input之后有一个机会停下来结算由最后一个bar组成的矩形的最大面积，否则如果是一直递增的bars，遍历完是没有机会停下来结算的。

这个题为什么可以用单调栈做，并且单调栈的思想适用于什么样的题目，我觉得是比如你在一堆单调增或者单调减的数据里面突然找一个拐点，就可以尝试利用单调栈。这个还是需要多做才有感觉。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int largestRectangleArea(int[] heights) {
 3         if (heights == null || heights.length == 0) {
 4             return 0;
 5         }
 6         Stack<Integer> stack = new Stack<>();
 7         int res = 0;
 8         for (int i = 0; i <= heights.length; i++) {
 9             int h = i == heights.length ? 0 : heights[i];
10             while (!stack.isEmpty() && h < heights[stack.peek()]) {
11                 int height = heights[stack.pop()];
12                 int start = stack.isEmpty() ? -1 : stack.peek();
13                 int area = height * (i - start - 1);
14                 res = Math.max(res, area);
15             }
16             stack.push(i);
17         }
18         return res;
19     }
20 }

JavaScript实现

 1 /**
 2  * @param {number[]} heights
 3  * @return {number}
 4  */
 5 var largestRectangleArea = function(heights) {
 6     // corner case
 7     if (heights == null || heights.length == 0) {
 8         return 0;
 9     }
10 
11     // normal case
12     let stack = [];
13     let res = 0;
14     for (let i = 0; i <= heights.length; i++) {
15         let h = i == heights.length ? 0 : heights[i];
16         while (stack.length && h < heights[stack[stack.length - 1]]) {
17             let height = heights[stack.pop()];
18             let start = !stack.length ? -1 : stack[stack.length - 1];
19             let area = height * (i - start - 1);
20             res = Math.max(res, area);
21         }
22         stack.push(i);
23     }
24     return res;
25 };

其他思路

暴力解，O(n^2)，OA也勉强能过，不会超时

Java实现

 1 class Solution {
 2     public int largestRectangleArea(int[] heights) {
 3         int len = heights.length;
 4         int area = 0;
 5         // 枚举左边界
 6         for (int left = 0; left < len; left++) {
 7             int minHeight = Integer.MAX_VALUE;
 8             // 枚举右边界
 9             for (int right = left; right < len; right++) {
10                 // 确定高度，我们要最小的高度
11                 minHeight = Math.min(minHeight, heights[right]);
12                 // 计算面积，我们要保留计算过的最大的面积
13                 area = Math.max(area, (right - left + 1) * minHeight);
14             }
15         }
16         return area;
17     }
18 }