leetcode-stack

84. Largest Rectangle in Histogram.py

class Solution:
    """
    Thought Process
        Brute Force:
        Two pointers:
            T: O(n^2)
            S: O(1)
        Stack:
            we use stack to maintain the minimum height on the left side of heights[i].
            And, the top of stack is closest index of minimum height.
            step1:We traverset the given height:
                If current height, heights[i], <= top of stack:
                    we calulate the area of rectangel formed using the height of top of stack.
                    to make sure top e top of stack is closest index of minimum height
                    width = i - stack[-1], wehre i is current index but in order to handle 0-index. intially, we put -1 in the stack.
                    
            step2:掃完heights之後如果stack不為空, 我們需要去掃右半邊可能的max arre  
                因為當前右邊的高度一定比top of stack還高
    """
    def largestRectangleArea(self, heights: List[int]) -> int:
        """
        Two pointers
        T: O(n^2)
        S: O(1)
        """
        n = len(heights)
        max_area = 0
        for i in range(n):
            min_height = float("inf")
            for j in range(i, n):
                min_height = min(min_height, heights[j])
                max_area = max(max_area, min_height* (j-i+1))
        return max_area
    
    def largestRectangleArea(self, heights: List[int]) -> int:
        """
        Stack
        T:O(n) because each index were push and pop at most once.
        S:O(n)
        """
        n = len(heights)
        stack = collections.deque([-1]) 
        max_area = 0
        for i in range(n):
            # think about case in decreasing order, then we know we need to append (-1) intially
            while stack[-1] != -1 and heights[stack[-1]] >= heights[i]:
                min_height_ix = stack.pop()
                cur_min_height = heights[min_height_ix]
                cur_width = i-1-stack[-1] # 1-1-(-1) = 1
                max_area = max(max_area, cur_min_height * cur_width)
            stack.append(i)
        # think about case in increasing order
        while stack[-1] != -1:
            min_height_ix = stack.pop()
            cur_min_height = heights[min_height_ix]
            cur_width = len(heights)-stack[-1] - 1
            max_area = max(max_area, cur_min_height * cur_width)
        return max_area