[LeetCode] 84. Largest Rectangle in Histogram

BaronZhang 發布于2019-08-16 14:25 / 1940人閱讀

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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