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.

histogram.png

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

histogram_area.png

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

分析:

本题比较经典,解法也十分巧妙。

首先:最大矩形的高度必然和某一个立柱的高度相等,或者说,最大矩形必然包含了某一个立柱的全部。
所以我们要依次计算包含完整立柱 i 的最大矩形面积。

以图中 i = 2(即立柱的高为5)为例。包含完整该立柱的最大矩形的面积为 5 * 2 = 10。5为该立柱的高度,那么2是怎么来的呢?

方法是:分别找出该立柱左右两边离它最近的高度小于它的立柱。两个下标相减再减一即可。例如,图中立柱 i = 2(高为5)左右两边离它最近且高度小于它的立柱分别是立柱 i = 1(高为1)和立柱 i = 4(高为2),4 - 1 - 1 = 2,所以包含完整立柱 i = 2 的最大矩形面积为 5 * (4 - 1 - 1)= 10。

同理,包含完整立柱 i = 3(高为6)的最大矩形面积为 6 * (4 - 2 - 1) = 6。

使用栈可以巧妙地实现该思路。

代码:

public class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<Integer>();
int maxArea = 0;
for (int i = 0; i <= heights.length; i++) {
int h = (i == heights.length ? 0 : heights[i]);
if (stack.isEmpty() || h >= heights[stack.peek()]) {
stack.push(i);
} else {
int temp = stack.pop();
maxArea = Math.max(maxArea, heights[temp] * (stack.isEmpty() ? i : i - 1 - stack.peek()));
i--;
}
}
return maxArea;
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :