[LeetCode] 84. Largest Rectangle in Histogram

Problem : https://leetcode.com/problems/largest-rectangle-in-histogram/

Solution 1 :

Iterate the input array until encounter a peak number ( number[i] > number[i+1] ), move backward to find the potential largest rectangle.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
    
    	result = 0
        N = len(heights)
       
        for i in range(N):
            # find peak where heights[i] > heights[i+1]
            if i == N -1 or heights[i] > heights[i+1]:
                minHeight = heights[i]
                # move backward to find potential largest rectangle
                for j in reversed(range(0, i+1)):
                    minHeight = min(minHeight, heights[j])
                    result = max(result, minHeight * (i - j + 1))
                    
        return result

Solution 2 :

Iterate the input array and push current height and its start index to stack if current height higher than top value of stack. Otherwise, pop stack and extend start index of current height to left until top value of stack less than current height.  Calculate the potential largest rectangle size while popping stack.

At last, clear up the stack and calculate rectangle size formed with the bar in stack and the end of histogram.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        result = 0
        stack = []
        
        for i, h in enumerate(heights):
            start = i
            
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                result = max(result, height * (i - index))
                
                # extend current short height index to left 
                start = index
                
            stack.append((start, h))
        
        # the remain heights are extended to end of histogram
        while stack:
            index, height = stack.pop()
            result = max(result, height * (len(heights) - index))
        
        return result