LeetCode Day 60 Monotonic Stack (3/3)

Today is the last day of training, I am feeling accomplished!

Question 1

84. Largest Rectangle in Histogram

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

To solve this problem using the monotonic stack idea, the problem is to find the first column to the left and right of each column that is smaller than that column, so the order from the head of the stack (where the elements are popped off the head) to the bottom of the stack should be in order from largest to smallest. The top of the stack and the next element from the top of the stack, as well as the three elements to go on the stack make up the height and width of the maximum area we require.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.insert(0, 0)
        heights.append(0)
        stack = [0]
        result = 0
        for i in range(1, len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                mid_height = heights[stack[-1]]
                stack.pop()
                if stack:
                    # area = width * height
                    area = (i - stack[-1] - 1) * mid_height
                    result = max(area, result)
            stack.append(i)
        return result