Leetcode84 Largest Rectangle Are

这道题网上有很多的答案，本文旨在加入一些我的理解，把问题说的更明白一些。

题目：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.
题目附带一个例子，给定数组[2,1,5,6,2,3]，该数组表示如下的形状：

图1

答案则是如下形状的面积，5*2=10，也就是图中存在的最大的矩形面积。

图2

解决问题的关键在于：以i位置（ai）结束的最大面积只由从i位置开始的紧密降序块集合决定。

接下来定义紧密降序块集合：给定数组a0,a1,...,an。那么ai，i=0,1,...,n，的紧密降序块集合，是指从i位置开始向前寻找，所有第一个比上一个找到的降序块低的块的序号构成的有序集合。

使用上图举例，a5（最后一个，3）的紧密降序块集合是[1,4,5]，因为这是从a5开始向前搜索，每次找到第一个相对于上一个块的低的块就进行添加的结果。同理a3的紧密降序块集合是[1,2,3]。

实际上，a0-ai的最大面积只由ai的紧密降序块集合决定。以a3为例，我们只需要计算如下三个面积。

图3 图4 图5

涉及的信息只是a1，a2，a3的高度和序号信息而已。考虑以a5为结尾的最大面积，发现虽然矩形可以从a0贯穿到a5，但a2，a3的高度完全没用，因为a1和a4这两个短板高度决定了矩形的高度。

了解这个原理后，事情就变得非常容易了。我们从a0遍历至an，并维护一个升序的栈（就是紧密降序块集合），这意味着栈顶永远比栈低大，每考虑一个值就试图计算以这个值结束的最大面积。如果遍历到的值大于栈顶，就入栈，此时没必要计算最大面积，因为后一个值比前一个值大的话，以后一个值结束的最大面积一定大于以前一个值结束的最大面积。否则退栈直到栈顶小于当前值。每退栈一次就进行一次面积清算。值得注意的是当退栈后栈空时，矩形的宽度是i（如图5），否则是由紧密降序块集合相邻元素的差决定。就上例而言，考虑a4时进行了两次退栈，进行了图3，图4所示的面积清算。进行面积清算时找到了以a3结束的最大面积。没有进行图5所示的清算的原因是a1仍是后面的紧密降序块集合的元素。

Talk is cheap，千言万语不能说清楚这一复杂过程。单步执行一下代码，你会更清楚。

//Java
import java.util.Stack;

public class Problem84 {

    public static int largestRectangleArea(int[] heights) {
        int[] heightsp = new int[heights.length + 1];
        for (int i = 0; i < heights.length; i++) {
            heightsp[i] = heights[i];
        }
        heightsp[heights.length] = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int rst = 0;
        for (int i = 1; i < heightsp.length; i++) {
            while (!stack.empty() && heightsp[stack.peek()] > heightsp[i]) {
                int popIdx = stack.pop();
                int width = stack.empty() ? i : i - stack.peek() - 1;
                int square = heights[popIdx] * width;
                if (square > rst)
                    rst = square;
            }
            stack.push(i);
        }
        return rst;
    }

    public static void main(String[] args) {
        int[] recs = new int[] {4,2,0,3,2,4};
        int s = largestRectangleArea(recs);
        System.out.println(s);
    }

}

欢迎你来我的github看一看，里面有我刷的leetcode源码，也许对你有用：https://github.com/nephashi/jobhunter/tree/master/src/algorithm/leetcode