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

資訊專欄INFORMATION COLUMN

Largest Rectangle in Histogram

vvpvvp / 2251人閱讀

摘要：而最大的矩形一定滿足兩個邊界的高度小于該矩形的高度這個條件如果不滿足的話，邊界也可以被添加進來計算而不破壞矩形的形狀，此時不為最大，因此找出所有這樣的矩形就一定可以在其中找出面積最大的矩形。

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.

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

Solution
暴力窮舉法

最簡單的自然是暴力法，即窮舉左端坐標和右端坐標，計算兩個坐標之間矩形的最大面積，再從所有的面積中得出最大的即為解。但是該方法至少需要兩個for循環來遍歷每一種左右端的組合，時間復雜度為O($n^2$)。以下是該方法的代碼，解是對的，但在leetcode上會超時。

class Solution:
    # @param height, a list of integer
    # @return an integer
    def largestRectangleArea(self, height):
        length = len(height)
        max_area = -1
        for i in range(length):
            for j in range(i + 1, length):
                h = min(height[i: j])
                area = h * (j - i)
                if max_area < area:
                    max_area = area
        return max_area
利用棧減小時間復雜度

可以考慮，計算一個矩形的面積時，比如圖

中的斜線部分，其兩側的高度一定是低于矩形所在的矩形條的高度的，因此可以通過維護一個棧來得出左端左邊及右端坐標和矩形的高度，每一個矩形條只進棧一次，這樣時間復雜度為O(n)。
1. 算法從左向右遍歷每個矩形，以當前遍歷的位置為右端坐標，如果棧為空或者當前矩形不低于棧頂的矩形，則將當前的位置坐標壓棧，因為此時的坐標一定不是右邊界（指要計算的面積右邊的一個矩形條，不包含在要計算的面積中），例如圖中，加入當前坐標為3，高度為6，棧頂坐標的高度為5，那么當前矩形條不可能作為右邊界，將其壓棧。
2. 如果當前位置的矩形低于棧頂的矩形條，那么當前位置可以作為一個矩形的邊界，則從這個位置開始向左遍歷，對每個高度大于右邊界的矩形條作為左邊界計算一次面積，直到高度小于右邊界或棧為空。
3. 在遍歷過一遍之后，如果棧不為空，則以棧中的每個坐標作為左邊界計算一次面積，結合步驟2得出最大面積。
Accepted code如下：

class Solution:
    # @param height, a list of integer
    # @return an integer
    def largestRectangleArea(self, height):
        max_area = 0
        i = 0
        n = len(height)
        stack = []
        while i < n:
            if len(stack) == 0 or height[i] >= height[stack[-1]]:
                stack.append(i)
                i += 1
            else:
                top = stack.pop()
                area_with_top = height[top] * (i if len(stack) == 0 else i - stack[-1] - 1)
                if max_area < area_with_top:
                    max_area = area_with_top

        while len(stack) != 0:
            top = stack.pop()
            area_with_top = height[top] * (i if len(stack) == 0 else i - stack[-1] - 1)
            if max_area < area_with_top:
                max_area = area_with_top

        return max_area

這個方法并不是提供一個準確的找出最大的矩形的算法，而是通過試驗那些“可能”成為最大的矩形的面積，再從其中找出最大的。而最大的矩形一定滿足兩個邊界的高度小于該矩形的高度這個條件（如果不滿足的話，邊界也可以被添加進來計算而不破壞矩形的形狀，此時不為最大），因此找出所有這樣的矩形就一定可以在其中找出面積最大的矩形。

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

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

  • [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 評論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元查看
<