84. Largest Rectangle in Histogram

Description

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.

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

思路

常规方法

我首先想到的是如何将这个问题缩小为多个子问题，问题在于如何分解为可解的问题

想到求0~n个bar中最大的矩形面积等于求解如下子问题：

求包含0~n个bar且面积最大的矩形
求0~n-1个bar中最大矩形面积
求1~n个bar中最大矩形面积

其中第1个子问题的解就是找到0~n个bar中最小的值乘n；2，3子问题都可以转为第一个子问题，找到这3个子问题的最大值，就为原问题的最大值；

这种递归问题会有重复的过程，因此要转为DP的形式求解，想到建立一个二维数组，行表示包含多少个连续的bar的最大面积，如下所示：

假设有5个bar，计算这样的矩阵：

	0	1	2	3	4
0	1	2	3	4	5
1	#	1，2	2，3	3，4	4，5
2	#	#	1，2，3	2，3，4	3，4，5
3	#	#	#	1,2,3,4	2,3,4,5
4	#	#	#	#	1,2,3,4,5

第一行和第一列表示的是下标，其中的值代表连续bar的最大矩阵，比如行下标为1，列下标为2中的值2，3 表示的是计算包含2，3且面积最大的矩阵

这样又涉及到一个问题，如何求连续bar的最小值，一般需要O(n)的复杂度，肯定不能放到for循环里面了，只能再建立一个矩阵，与上面对应，只是其中的含义变了，比如计算下标为(2,3)中bar的最小值，可以由(1,2),(1,3)得到：

$flag[i][j]=min(flag[i-1][j-1],flag[i-1][j])$

这样，思路就讲完了，具体实现代码如下：

public static int largestRectangleArea(int[] heights) {
    int maxSum=0;
    int n=heights.length;
    int[][] minValue=new int[n][n];
    int[][] sumMat=new int[n][n];
    //求相邻区域中heights的最小值
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            if(i==0)minValue[i][j]=heights[j];
            else minValue[i][j]=Math.min(minValue[i-1][j-1],minValue[i-1][j]);
            System.out.print(minValue[i][j]+",");
        }
        System.out.println();
    }
    //求全部情况能组成长方形的最大值
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            if(i==0)sumMat[i][j]=heights[j];
            else sumMat[i][j]=(i+1)*minValue[i][j];
            if(maxSum<sumMat[i][j])maxSum=sumMat[i][j];
            System.out.print(sumMat[i][j]+",");
        }
        System.out.println();
    }
    return maxSum;
}

O(n)的实现

1) Create an empty stack.

2) Start from first bar, and do following for every bar ‘hist[i]’ where ‘i’ varies from 0 to n-1.
……a) If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack.
……b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).

3) If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.

Following is implementation of the above algorithm.

即：

遍历全部元素i：

如果栈空或者栈顶元素小于当前下标为i的元素，将i号元素进栈
否则，出栈，计算最大面积和此时计算的矩形面积比较

关于此时计算的矩形面积：当前i-1和栈顶元素的差乘以出栈下标对应的元素，如果栈空，则用i乘以出栈下标对应的元素

比较难理解，给出几篇参考文章：

下面是leetcode上的代码，结合第一篇文章，很好理解

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