84. Largest Rectangle in Histogram

melody_lql 發布于2019-08-14 18:01 / 3450人閱讀

摘要：要求一個矩形的面積，要知道高和寬。如果每次確定高度為然后調用一個找到左右邊界，即不小于的最左和最右。這是一個明顯的算法，每次掃描都會重走整個。一個遞增序列這種，我們知道可以夠成的矩形是會不斷增大的。遞增序列預處理，遞減的時候計算。

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

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

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