Largest Rectangle in Histogram 解答

Question

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

Example

Given height = [2,1,5,6,2,3],
return 10.

Solution 1 -- Naive

For each start point i

　　For each end point j

　　　　minHeight = min height between i and j

　　　　result = max{result, (j - i + 1) * minHeight}

Time Complexity O(n²)

 public class Solution {

     /**

      * @param height: A list of integer

      * @return: The area of largest rectangle in the histogram

      */

     public int largestRectangleArea(int[] height) {

         // write your code here

         if (height == null || height.length < 1)

             return 0;

         int start, end, minHeight, result = Integer.MIN_VALUE;

         for (start = 0; start < height.length; start++) {

             minHeight = height[start];

             for (end = start; end < height.length; end++) {

                 minHeight = Math.min(minHeight, height[end]);

                 result = Math.max(result, (end - start + 1) * minHeight);

             }

         }

         return result;

     }

 }

Solution 2 -- Increasing Stack

根据木桶原理，面积由最矮的高度决定。我们把问题转换为

For 决定矩阵高度的那根最矮木头 i

　　看 i 往左最远能延伸到什么地方 indexLeft

　　看 i 往右最远能延伸到什么地方 indexRight

　　best = max{best, height[i] * (indexRight - indexLeft + 1)}

所以我们要找：

往左走第一个比height[i]小的数

往右走第一个比height[i]小的数

这种题典型的用递增／递减栈实现。

 public class Solution {

     /**

      * @param height: A list of integer

      * @return: The area of largest rectangle in the histogram

      */

     public int largestRectangleArea(int[] height) {

         // write your code here

         if (height == null || height.length < 1)

             return 0;

         int result = 0;

         Stack<Integer> increasingStack = new Stack<Integer>();

         // Attention here i <= length

         for (int i = 0; i <= height.length; i++) {

             int currentValue = ((i == height.length) ? -1 : height[i]);

             while (!increasingStack.isEmpty() && height[increasingStack.peek()] >= currentValue) {

                 int currentHeight = height[increasingStack.pop()];

                 int left = increasingStack.size() > 0 ? increasingStack.peek() : -1;

                 int right = i;

                 result = Math.max(result, (right - left - 1) * currentHeight);

             }

             increasingStack.push(i);

         }

         return result;

     }

 }

注意，这里除了要计算以每个pop出来的元素为高的最大面积，还要计算每个未被pop出来的元素为高的最大面积。因此技巧在于最后多加一个元素-1，由于输入元素均大于等于0，所以当-1要push入栈时，栈里所有的元素都会被pop出来。

还要注意，当前值等于栈顶值时也要做出栈操作。

每个元素只入栈／出栈一次，因此时间复杂度是O(1)

巴特西

Largest Rectangle in Histogram 解答

Question

Solution 1 -- Naive

Solution 2 -- Increasing Stack

最新文章

热门文章