Largest Rectangle in Histogram

vvpvvp 發(fā)布于2019-07-24 17:33 / 2255人閱讀

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

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

暴力窮舉法

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

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

利用棧減小時(shí)間復(fù)雜度

可以考慮，計(jì)算一個(gè)矩形的面積時(shí)，比如圖

中的斜線部分，其兩側(cè)的高度一定是低于矩形所在的矩形條的高度的，因此可以通過維護(hù)一個(gè)棧來得出左端左邊及右端坐標(biāo)和矩形的高度，每一個(gè)矩形條只進(jìn)棧一次，這樣時(shí)間復(fù)雜度為O(n)。
1. 算法從左向右遍歷每個(gè)矩形，以當(dāng)前遍歷的位置為右端坐標(biāo)，如果棧為空或者當(dāng)前矩形不低于棧頂?shù)木匦危瑒t將當(dāng)前的位置坐標(biāo)壓棧，因?yàn)榇藭r(shí)的坐標(biāo)一定不是右邊界（指要計(jì)算的面積右邊的一個(gè)矩形條，不包含在要計(jì)算的面積中），例如圖中，加入當(dāng)前坐標(biāo)為3，高度為6，棧頂坐標(biāo)的高度為5，那么當(dāng)前矩形條不可能作為右邊界，將其壓棧。
2. 如果當(dāng)前位置的矩形低于棧頂?shù)木匦螚l，那么當(dāng)前位置可以作為一個(gè)矩形的邊界，則從這個(gè)位置開始向左遍歷，對(duì)每個(gè)高度大于右邊界的矩形條作為左邊界計(jì)算一次面積，直到高度小于右邊界或棧為空。
3. 在遍歷過一遍之后，如果棧不為空，則以棧中的每個(gè)坐標(biāo)作為左邊界計(jì)算一次面積，結(jié)合步驟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

這個(gè)方法并不是提供一個(gè)準(zhǔn)確的找出最大的矩形的算法，而是通過試驗(yàn)?zāi)切翱赡堋背蔀樽畲蟮木匦蔚拿娣e，再從其中找出最大的。而最大的矩形一定滿足兩個(gè)邊界的高度小于該矩形的高度這個(gè)條件（如果不滿足的話，邊界也可以被添加進(jìn)來計(jì)算而不破壞矩形的形狀，此時(shí)不為最大），因此找出所有這樣的矩形就一定可以在其中找出面積最大的矩形。