[LeetCode] 84. Largest Rectangle in Histogram

BaronZhang 发布于2019-08-16 14:25 / 1858人阅读

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.

Solution

class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) return 0;
        int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];
        right[n-1] = n;
        left[0] = -1;
        for (int i = 1; i < n; i++) {
            int index = i-1;
            while (index >= 0 && height[index] >= height[i]) index = left[index];
            left[i] = index;
        }
        for (int i = n-2; i >= 0; i--) {
            int index = i+1;
            while (index < n && height[index] >= height[i]) index = right[index];
            right[i] = index;
        }
        int max = 0;
        for (int i = 0; i < n; i++) max = Math.max(max, height[i]*(right[i]-left[i]-1));
        return max;
    }
}

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

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

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

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
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