国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LintCode] Largest Rectangle in Histogram

alighters / 2370人閱讀

摘要：只要出現當前右邊界高度小于等于棧頂元素高度的情況，就取出棧頂元素當前遍歷過最高的并對這個元素進行取最大矩形的運算。

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.

Example

Given height = [2,1,5,6,2,3],
return 10.

Note

第二遍幾乎已經忘記這道題的做法了，while循環看起來過于復雜。起來重新看了一下LC的論壇，整理一下這個做法的思路。
首先，如何比較最大面積max，怎樣減省運算的次數，什么情況下向stack放入元素？
計算面積，可以用右邊界和左邊界之差，乘以兩邊界之間的最小高度。計算最大面積，則需要從左向右遍歷所有點作為右邊界，逐一計算每個右邊界可以圍成的最大面積，每次循環取最大值即可。
簡化運算，需要用一個堆棧stack。若stack為空或當前右邊界高度大于stack棧頂所存的右邊界高度，則將當前右邊界坐標i壓入棧頂。這樣做的結果就是，堆棧從棧底到棧頂，所存的右邊界高度一定是遞增的。只要出現當前右邊界高度小于等于棧頂元素高度的情況，就取出棧頂元素（當前遍歷過最高的height[i]）并對這個元素進行取最大矩形的運算。此后，這個被pop出的棧頂最大元素不會影響之后運算的結果（作為最大高度的所有情況已經在while循環里運算和比較過最大值了）。
分析邊界情況：遍歷的點i對應的最大矩形，是stack.pop()，也就是它的前一個點i-1作為右邊界時的最大矩形，所以i要循環到height.length。當i循環到height.length的時候，令cur = 0，以確保cur小于等于height[stack.peek()]，即height[]的最后一個元素。另外，計算矩形寬度的時候，要考慮是不是height[0]：如果是，那么賦值h為height[stack.pop()]之后，stack為空，寬度w自動賦1。其它情況下，w = i-1-stack.peek()

例如[3,4,5,4,3]， 在i = 3，cur = 4的時候，第一次出現高度遞減的情況。此時最大面積是前三個元素圍成的矩形，max = 5 * (3-1-1) = 5，然后進行第二次while循環：max = Math.max(5, 4 * (3-1-0)) = 8，此時，cur大于stack中最后一個元素3，跳出while循環，將cur的坐標壓入stack，繼續遍歷。當i = 4，cur = 3，再次進入while循環，max = Math.max(8, 4*(4-0-1)) = 12，然后進行第二次while循環：max = Math.max(12, 3 * 4) = 12，跳出循環，并將i = 4放入已經為空的堆棧。最后一輪while循環：max = Math.max(12, 3 * 5) = 15。返回15.

最后的建議是，多寫幾遍，自然就理解了。

Solution 
public class Solution {
    public int largestRectangleArea(int[] height) {
        Stack stack = new Stack();
        int max = 0;
        for (int i = 0; i <= height.length; i++) {
            int cur = i == height.length ? 0 : height[i];
            while (!stack.isEmpty() && cur <= height[stack.peek()]) {
                int h = height[stack.pop()];
                int w = stack.isEmpty() ? i : i-1-stack.peek();
                max = Math.max(max, h*w);
            }
            stack.push(i);
        }
        return max;
    }
}

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

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

    鄒強 評論0 收藏0

  • Largest Rectangle in Histogram

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

    vvpvvp 評論0 收藏0

  • leetcode84. Largest Rectangle in Histogram

    摘要：題目要求即找到圖中可以組合而成的面積最大的矩形。從而我們可以知道該矩形在水平方向上的最大擴展程度。也就是說，棧中數據記錄了最遠左側下標，而當前的矩形則是最遠右側下標。當我們不采用數據結構時，尋找和計算的過程需要的時間復雜度。 題目要求 Given n non-negative integers representing the histograms bar height where t...

    Harpsichord1207 評論0 收藏0

  • 84. Largest Rectangle in Histogram

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

    melody_lql 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<