84. Largest Rectangle in Histogram

melody_lql 发布于2019-08-14 18:01 / 3346人阅读

摘要：要求一个矩形的面积，要知道高和宽。如果每次确定高度为然后调用一个找到左右边界，即不小于的最左和最右。这是一个明显的算法，每次扫描都会重走整个。一个递增序列这种，我们知道可以够成的矩形是会不断增大的。递增序列预处理，递减的时候计算。

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

要求一个矩形的面积，要知道高和宽。
如果每次确定高度为height[i], 然后调用一个helper function找到左右边界，即不小于height[i]的最左和最右。
这是一个明显O(N^2)的算法，每次扫描都会重走整个array。
这里有些步骤是不必要的，比如高度为2往左扫的时候已经知道2>1了，然当高度为1的时候，不必往左走，我们可以通过空间来记忆已知信息。
一个递增序列156这种，我们知道可以够成的矩形是会不断增大的。而当1562,遇到2的时候矩形可能变小，这时我们就要计算面积了。
递增序列预处理，递减的时候计算。

用代码打印出每步的结果。
height : 0 left :0 right : 1 cur 2 area : 2
height : 3 left :3 right : 4 cur 6 area : 6
height : 2 left :2 right : 4 cur 10 area : 10
height : 5 left :5 right : 6 cur 3 area : 10
height : 4 left :2 right : 6 cur 8 area : 10
height : 1 left :0 right : 6 cur 6 area : 10

public class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack stk = new Stack<>();
        int area = 0;
        for(int i=0; i<= heights.length; i++){
            int h = i == heights.length ? 0 : heights[i];
            if(stk.isEmpty() || h >= heights[stk.peek()]){
                stk.push(i);
            } else {
                int top = stk.pop();
                // 为什么用stk.peek()+1, 因为这里stack里存的可能不连续。
                area = Math.max(area, heights[top]*(stk.isEmpty()? i: i-(stk.peek()+1)));
                i--;
            }
        }
        return area;
    }

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

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

转载请注明本文地址：https://www.ucloud.cn/yun/66942.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
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
[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
[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
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