美文网首页
Leetcode84 Largest Rectangle Are

Leetcode84 Largest Rectangle Are

作者: nepha | 来源:发表于2018-07-20 23:38 被阅读0次

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

    题目: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

    相关文章

      网友评论

          本文标题:Leetcode84 Largest Rectangle Are

          本文链接:https://www.haomeiwen.com/subject/illcmftx.html