lc-monotone stack

84. Largest Rectangle in Histogram.py

class Solution:
    """
    Brute Force: 已當前高度為邊界,去找出所有可能的rectangle
        we traverse the array.
        For each cur_h, we enumerate all valid rectangle and calculater area
        by w * min_h in the subarray.
        T:O(n^2)
        S:O(1)
    
    Can we optimise?
    
    已當前高度為邊界,去找出所有可能的rectangle
    只有之前高度比他高的histogram可以expand his width till cur width.
    想到Monotone stack
    maintain a increasing stack
    [1,2,3,2]
    """
    def largestRectangleArea(self, nums: List[int]) -> int:
        """
        T:O(n^3)
        """
        n = len(nums)
        rec = float("-inf")
        for i in range(n):
            if i == 0:
                rec = max(rec, nums[i])
                continue
            # edge case: w = 1
            rec = max(rec, nums[i])
            for j in range(i):
                w = i-j+1
                min_h = min(nums[j:i+1])
                rec_a = w * min_h
                rec = max(rec, rec_a)
        return rec
    
    def largestRectangleArea(self, nums: List[int]) -> int:
        nums.append(0)
        n = len(nums)
        rec = float("-inf")
        stack = []
        for i in range(n):
            cur_h = nums[i]
            if i == 0:
                rec = max(rec, cur_h)
                stack.append((cur_h, i))
                continue
            # edge case: w = 1
            rec = max(rec, cur_h)
            while stack and stack[-1][0] > cur_h:
                min_h = stack.pop()[0]
                # 此width和次頂元素的位置有關
                if stack:
                    w = i-stack[-1][1]-1 # 不包含當前元素, 也不能包含次頂元素因為他比較小
                else:
                    w = i-1+1
                rec_a = w * min_h
                rec = max(rec, rec_a)
            stack.append((cur_h, i))
        # 因為沒有遇到一個最小的元素, 我們只要一開始在nums後面+一個最小元素, 強制最後一定會把棧的元素出空
        return rec