leetcode: 84. Largest Rectangle in Histogram -开发者知识库

leetcode: 84. Largest Rectangle in Histogram -开发者知识库,第1张

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.

leetcode: 84. Largest Rectangle in Histogram -开发者知识库,這里寫圖片描述,第2张

# Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

leetcode: 84. Largest Rectangle in Histogram -开发者知识库,這里寫圖片描述,第3张

# The largest rectangle is shown in the shaded area, which has area = 10 unit.
#
# For example,
# Given heights = [2,1,5,6,2,3],
# return 10.

Idea

仔細考察Brute Force算法,發現問題在於指針重復掃描。以遞增序列為例:

0 1 2 3 4 5 6

在計算s[0]的時候掃描了右邊6個數,計算s[1]時繼續掃描右邊5個數,依次類推。而沒能利用到這個序列的遞增性質。當序列從i遞增到j時,bar i~j的面積一定都能擴展到j。而一旦在j 1遞減了,那么表示bar i~j中的部分bar k無法繼續擴展,條件是h[k]>h[j 1]。

1. 利用這個性質,可以將遞增序列cache在一個stack中,一旦遇到遞減,則根據h[j 1]來依次從stack里pop出那些無法繼續擴展的bar k,並計算面積。

2. 由於面積的計算需要同時知道高度和寬度,所以在stack中存儲的是序列的坐標而不是高度。因為知道坐標后很容易就能知道高度,而反之則不行。

AC

class Solution():
    def largestRectangleArea(self, xs):
        xs.insert(0, 0)
        xs.append(0)
        stack, maxArea = [], 0
        for i, x in enumerate(xs):
            if not stack or xs[stack[-1]] <= x:
                stack.append(i)
            else:
                while stack and xs[stack[-1]] > x:
                    maxArea = max(maxArea, xs[stack[-1]]*(i-stack[-2]-1))
                    stack.pop()
                stack.append(i)
        right = stack[-1]
        stack.pop()
        while len(stack) > 1:
            offset = right-stack[-1]
            maxArea = max(maxArea, xs[stack[-1]]*offset)
            stack.pop()
        return maxArea


if __name__ == "__main__":
    assert Solution().largestRectangleArea([2, 0, 2]) == 2
    assert Solution().largestRectangleArea([2, 1, 5, 6, 2, 3]) == 10

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复