leetcode84. Largest Rectangle in Histogram

Harpsichord1207 发布于2019-08-15 10:55 / 1259人阅读

摘要：题目要求即找到图中可以组合而成的面积最大的矩形。从而我们可以知道该矩形在水平方向上的最大扩展程度。也就是说，栈中数据记录了最远左侧下标，而当前的矩形则是最远右侧下标。当我们不采用数据结构时，寻找和计算的过程需要的时间复杂度。

题目要求

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.

即找到图中可以组合而成的面积最大的矩形。

这里我首先想到的是leetcode 42 Trapping Rain Water，可以参考我的这篇博客。
因为在42题中，如果我找到了当前矩形左右的最近最高矩形即可。而在本题中，同样是需要找到该矩形左右的最高矩形，但不同的是，一旦我在左右搜寻的过程中遇到了一个比当前矩形矮的矩形，遍历即结束。所以两道题目的要求还是存在区别的。

思路一：直观但超时

最直观的思路也就是从当前矩形出发，分别向左向右遍历，一旦遇到一个矩形比当前矩形矮，则该方向的遍历结束。从而我们可以知道该矩形在水平方向上的最大扩展程度。代码如下：

    public int largestRectangleArea(int[] heights) {
        int barCount = heights.length;
        
        int max = 0;
        for(int i = 0 ; i=0 && heights[j]>=tempHeight ; j--) tempWidth++;
            for(int j = i+1 ; j=tempHeight ; j++) tempWidth++;
            max = Math.max(max, tempWidth*tempHeight);
        }
        return max;
    }

当然，该方法鉴于其需要O(n^2)的时间复杂度，再加上如果出现极端情况即每个矩形都可以水平扩展至n长度，其中n等于数组的长度（例如[1,1,1,1,......,1],n=100000），这样就会带来很多无效的遍历。

思路二：堆栈

如果我们按照顺序从左往右遍历，我们会返现，一旦右边的矩形比左边矮，则左边矩形的向右扩展的程度直接由右边矩形决定。那么我们如何知道左边矩形的左边扩展程度呢。这就需要我们采用栈的模式来记录。一旦新遇到的矩形比栈顶元素矮，我们需要逐个排出栈元素直到栈顶元素大于当前矩形高度。同时我们还需要将当前矩形的数据压入栈中，而当前矩形的左边距则由排出的最后元素的下标决定。也就是说，栈中数据记录了最远左侧下标，而当前的矩形则是最远右侧下标。代码如下：

    public int largestRectangleArea2(int[] heights){
        int barCount = heights.length;
        int max = 0;
        LinkedList stack = new LinkedList();
        for(int i = 0 ; itempHeight){
                lastIndex = stack.pop();
                max = Math.max(max, (i-lastIndex)*heights[lastIndex]);
                heights[lastIndex] =tempHeight; 
            }
            stack.push(lastIndex);
        }
        while(!stack.isEmpty()){
            int currentIndex = stack.pop();
            max = Math.max(max, (barCount-currentIndex)*heights[currentIndex]);
        }
        return max;
    }

思路三：利用已有数据删减遍历

这里我们延续一种的思路，还是采用找到当前矩形的最远左右侧下标，不同的是，我们用两个数据结构int[] lessFromLeft, int[] lessFromRight分别来存储当前矩形的最远左右侧下标。当我们不采用数据结构时，寻找和计算的过程需要O(n^2）的时间复杂度。而通过数据结构，我们可以很大程度上减少遍历次数，对当前矩阵的最左侧下标可以通过lessFromLeft跳跃遍历。也就是说，如果左侧矩形比当前矩形大，则跳到左侧矩形的最左侧矩形继续判断，如果最后调到起点，则结束遍历。

代码如下：

    public int largestRectangleArea3(int[] heights){
        int barCount = heights.length;
        if(barCount==0) return 0;
        int[] lessThanLeft = new int[barCount];
        int[] lessThanRight = new int[barCount];
        lessThanLeft[0] = -1;
        lessThanRight[barCount-1] = barCount;
        for(int i = 1 ; i=0 && heights[p]>=heights[i]){
                p = lessThanLeft[p];
            }
            lessThanLeft[i] = p;
        }
        for(int i = barCount-2 ; i>=0 ; i--){
            int p = i+1;
            while(p=heights[i]) p = lessThanRight[p];
            lessThanRight[i] = p;
        }
        
        int max = 0;
        for(int i = 0 ; i

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

私有云云服务器 HISTOGRAM Largest asp84教程 Rectangle

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67424.html

[LeetCode] 84. Largest Rectangle in Histogram

Problem Given n non-negative integers representing the histograms bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. showImg(https://segmentfault.com/img...

BaronZhang 2019-08-16 14:25 评论0 收藏0
[Leetcode] Largest Rectangle (in Histogram) 最大矩形

摘要：以此类推，如果一直到栈为空时，说明刚出来的竖条之前的所有竖条都比它自己高，不然不可能栈为空，那我们以左边全部的宽度作为长方形的宽度。 Largest Rectangle in Histogram Given n non-negative integers representing the histograms bar height where the width of each bar...

邹强 2019-08-14 12:24 评论0 收藏0
84. Largest Rectangle in Histogram

摘要：要求一个矩形的面积，要知道高和宽。如果每次确定高度为然后调用一个找到左右边界，即不小于的最左和最右。这是一个明显的算法，每次扫描都会重走整个。一个递增序列这种，我们知道可以够成的矩形是会不断增大的。递增序列预处理，递减的时候计算。 showImg(https://segmentfault.com/img/bVoQel); For example, Given heights = [2,...

melody_lql 2019-08-14 18:01 评论0 收藏0
Largest Rectangle in Histogram

摘要：而最大的矩形一定满足两个边界的高度小于该矩形的高度这个条件如果不满足的话，边界也可以被添加进来计算而不破坏矩形的形状，此时不为最大，因此找出所有这样的矩形就一定可以在其中找出面积最大的矩形。 Problem Given n non-negative integers representing the histograms bar height where the width of e...

vvpvvp 2019-07-24 17:33 评论0 收藏0
[LintCode] Largest Rectangle in Histogram

摘要：只要出现当前右边界高度小于等于栈顶元素高度的情况，就取出栈顶元素当前遍历过最高的并对这个元素进行取最大矩形的运算。 Problem Given n non-negative integers representing the histograms bar height where the width of each bar is 1, find the area of largest ...

alighters 2019-08-14 15:27 评论0 收藏0