[LintCode] Largest Rectangle in Histogram

alighters 发布于2019-08-14 15:27 / 2281人阅读

摘要：只要出现当前右边界高度小于等于栈顶元素高度的情况，就取出栈顶元素当前遍历过最高的并对这个元素进行取最大矩形的运算。

Problem

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.

Example

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

Note

第二遍几乎已经忘记这道题的做法了，while循环看起来过于复杂。起来重新看了一下LC的论坛，整理一下这个做法的思路。
首先，如何比较最大面积max，怎样减省运算的次数，什么情况下向stack放入元素？
计算面积，可以用右边界和左边界之差，乘以两边界之间的最小高度。计算最大面积，则需要从左向右遍历所有点作为右边界，逐一计算每个右边界可以围成的最大面积，每次循环取最大值即可。
简化运算，需要用一个堆栈stack。若stack为空或当前右边界高度大于stack栈顶所存的右边界高度，则将当前右边界坐标i压入栈顶。这样做的结果就是，堆栈从栈底到栈顶，所存的右边界高度一定是递增的。只要出现当前右边界高度小于等于栈顶元素高度的情况，就取出栈顶元素（当前遍历过最高的height[i]）并对这个元素进行取最大矩形的运算。此后，这个被pop出的栈顶最大元素不会影响之后运算的结果（作为最大高度的所有情况已经在while循环里运算和比较过最大值了）。
分析边界情况：遍历的点i对应的最大矩形，是stack.pop()，也就是它的前一个点i-1作为右边界时的最大矩形，所以i要循环到height.length。当i循环到height.length的时候，令cur = 0，以确保cur小于等于height[stack.peek()]，即height[]的最后一个元素。另外，计算矩形宽度的时候，要考虑是不是height[0]：如果是，那么赋值h为height[stack.pop()]之后，stack为空，宽度w自动赋1。其它情况下，w = i-1-stack.peek()

例如[3,4,5,4,3]，在i = 3，cur = 4的时候，第一次出现高度递减的情况。此时最大面积是前三个元素围成的矩形，max = 5 * (3-1-1) = 5，然后进行第二次while循环：max = Math.max(5, 4 * (3-1-0)) = 8，此时，cur大于stack中最后一个元素3，跳出while循环，将cur的坐标压入stack，继续遍历。当i = 4，cur = 3，再次进入while循环，max = Math.max(8, 4*(4-0-1)) = 12，然后进行第二次while循环：max = Math.max(12, 3 * 4) = 12，跳出循环，并将i = 4放入已经为空的堆栈。最后一轮while循环：max = Math.max(12, 3 * 5) = 15。返回15.

最后的建议是，多写几遍，自然就理解了。

Solution

public class Solution {
    public int largestRectangleArea(int[] height) {
        Stack stack = new Stack();
        int max = 0;
        for (int i = 0; i <= height.length; i++) {
            int cur = i == height.length ? 0 : height[i];
            while (!stack.isEmpty() && cur <= height[stack.peek()]) {
                int h = height[stack.pop()];
                int w = stack.isEmpty() ? i : i-1-stack.peek();
                max = Math.max(max, h*w);
            }
            stack.push(i);
        }
        return max;
    }
}

云服务器私有云 HISTOGRAM Largest LintCode Rectangle

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

转载请注明本文地址：https://www.ucloud.cn/yun/65771.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
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
leetcode84. Largest Rectangle in Histogram

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

Harpsichord1207 2019-08-15 10:55 评论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