Classic Problems

1. Largest Rectangle in Histogram

def largestRectangleArea(heights):
    """Find largest rectangle area in histogram"""
    stack = []
    max_area = 0

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    while stack:
        height = heights[stack.pop()]
        width = len(heights) if not stack else len(heights) - stack[-1] - 1
        max_area = max(max_area, height * width)

    return max_area

2. Trapping Rain Water

def trap(height):
    """Calculate trapped rainwater"""
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1

    return water

3. Remove K Digits

def removeKdigits(num, k):
    """Remove k digits to get smallest number"""
    stack = []

    for digit in num:
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)

    # Remove remaining k digits
    if k > 0:
        stack = stack[:-k]

    # Remove leading zeros
    result = ''.join(stack).lstrip('0')
    return result if result else '0'

Key Takeaway

These problems demonstrate how monotonic structures efficiently solve optimization problems involving order and comparisons.