[LeetCode] 84. Largest Rectangle in Histogram

BaronZhang 發(fā)布于2019-08-16 14:25 / 1941人閱讀

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云服務(wù)器云服務(wù)器 HISTOGRAM Largest asp84教程 Rectangle

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/72991.html

相關(guān)文章

leetcode84. Largest Rectangle in Histogram

摘要：題目要求即找到圖中可以組合而成的面積最大的矩形。從而我們可以知道該矩形在水平方向上的最大擴(kuò)展程度。也就是說(shuō)，棧中數(shù)據(jù)記錄了最遠(yuǎn)左側(cè)下標(biāo)，而當(dāng)前的矩形則是最遠(yuǎn)右側(cè)下標(biāo)。當(dāng)我們不采用數(shù)據(jù)結(jié)構(gòu)時(shí)，尋找和計(jì)算的過(guò)程需要的時(shí)間復(fù)雜度。題目要求 Given n non-negative integers representing the histograms bar height where t...

Harpsichord1207 2019-08-15 10:55 評(píng)論0 收藏0
[Leetcode] Largest Rectangle (in Histogram) 最大矩形

摘要：以此類推，如果一直到棧為空時(shí)，說(shuō)明剛出來(lái)的豎條之前的所有豎條都比它自己高，不然不可能棧為空，那我們以左邊全部的寬度作為長(zhǎng)方形的寬度。 Largest Rectangle in Histogram Given n non-negative integers representing the histograms bar height where the width of each bar...

鄒強(qiáng) 2019-08-14 12:24 評(píng)論0 收藏0
84. Largest Rectangle in Histogram

摘要：要求一個(gè)矩形的面積，要知道高和寬。如果每次確定高度為然后調(diào)用一個(gè)找到左右邊界，即不小于的最左和最右。這是一個(gè)明顯的算法，每次掃描都會(huì)重走整個(gè)。一個(gè)遞增序列這種，我們知道可以夠成的矩形是會(huì)不斷增大的。遞增序列預(yù)處理，遞減的時(shí)候計(jì)算。 showImg(https://segmentfault.com/img/bVoQel); For example, Given heights = [2,...

melody_lql 2019-08-14 18:01 評(píng)論0 收藏0
Largest Rectangle in Histogram

摘要：而最大的矩形一定滿足兩個(gè)邊界的高度小于該矩形的高度這個(gè)條件如果不滿足的話，邊界也可以被添加進(jìn)來(lái)計(jì)算而不破壞矩形的形狀，此時(shí)不為最大，因此找出所有這樣的矩形就一定可以在其中找出面積最大的矩形。 Problem Given n non-negative integers representing the histograms bar height where the width of e...

vvpvvp 2019-07-24 17:33 評(píng)論0 收藏0
[LintCode] Largest Rectangle in Histogram

摘要：只要出現(xiàn)當(dāng)前右邊界高度小于等于棧頂元素高度的情況，就取出棧頂元素當(dāng)前遍歷過(guò)最高的并對(duì)這個(gè)元素進(jìn)行取最大矩形的運(yùn)算。 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 評(píng)論0 收藏0