'''
keys: 
Solutions:
Similar:
T:
S:
'''
from typing import List

class Solution:
    
    # a concise version of stack
    #https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/28917/AC-Python-clean-solution-using-stack-76ms
    '''when a bar is popped out from the stack, we know it must be higher than 
    the bar at position i, so bar[i] must be the right boundary (exclusive) of 
    the rectangle, and the previous bar in the stack is the first one that is 
    shorter than the popped one so it must be the left boundary (also exclusive).
    Then we find the rectangle.'''
    def largestRectangleArea4(self, heights: List[int]) -> int:
        # for some heights there is no any other lower height at its right side.
        # Adding a 0 at the last makes all rectangles able to find their 
        # right-side boundary.
        heights.append(0)
        stack = [-1]
        maxArea = 0
        for i in range(len(heights)):
            while heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] - 1
                maxArea = max(maxArea, h * w)
            stack.append(i)
        heights.pop() # pop the 0 one added on the top, works even wo it
        return maxArea
    
    
    # using stack, O(n) for S and T
    def largestRectangleArea3(self, heights: List[int]) -> int:
        stack = [-1]
        maxArea = 0
        for i in range(len(heights)):
            while stack[-1] != -1 and heights[i] <= heights[stack[-1]]:
                maxArea = max(maxArea, heights[stack.pop()]*(i - stack[-1] - 1))
            stack.append(i)
            
        while stack[-1] != -1:
            maxArea = max(maxArea, heights[stack.pop()]*len(heights)-stack[-1]-1)
        return maxArea
                
    

    # divide and conquer, TLE
    # T: ave: O(nlogn), worst: O(n^2)
    # S: O(n) for the recursion depth n
    def helper(self, heights, start, end):
        if start > end:
            return 0
        minindex = start
        for i in range(start, end+1):
            if heights[minindex] > heights[i]:
                minindex = i # find the min height
        return max(heights[minindex] * (end - start + 1),\
               max(self.helper(heights, start, minindex-1),\
                self.helper(heights, minindex+1, end)))
        
    def largestRectangleArea2(self, heights: List[int]) -> int:
        return self.helper(heights, 0, len(heights)-1)
        
    
    # T: O(n^2) brutal force, TLE; S: O(1)
    # find the bar of minimum height for current pair 
    # by using the minimum height bar of the previous pair.
    def largestRectangleArea1(self, heights: List[int]) -> int:
        maxarea = 0
        for i in range(len(heights)):
            minheight = float("inf")
            for j in range(i, len(heights)):
                minheight = min(minheight, heights[j])
                maxarea = max(maxarea, minheight * (j-i+1))
        return maxarea
        
        
    # brutal force, TLE
    # T: O(n^3), S: O(1)
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxarea = 0
        for i in range(len(heights)):
            for j in range(i, len(heights)):
                minheight = float("inf")
                for k in range(i, j+1):
                    minheight = min(minheight, heights[k])
                maxarea = max(maxarea, minheight * (j-i+1))
        return maxarea
