Stack Pattern Guide for LeetCode

1. Core Stack Templates

Template 1: Basic Stack Operations

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        self.stack.append(x)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        return None

    def is_empty(self):
        return len(self.stack) == 0

Template 2: Monotonic Stack (Increasing)

def monotonic_increasing(arr):
    stack = []  # Maintains increasing order
    result = []

    for i, num in enumerate(arr):
        # Pop elements larger than current
        while stack and arr[stack[-1]] > num:
            result.append(stack.pop())
        stack.append(i)

    return result

Template 3: Monotonic Stack (Decreasing)

def monotonic_decreasing(arr):
    stack = []  # Maintains decreasing order
    result = []

    for i, num in enumerate(arr):
        # Pop elements smaller than current
        while stack and arr[stack[-1]] < num:
            result.append(stack.pop())
        stack.append(i)

    return result

2. LeetCode Problem Categories

Category 1: Parentheses Problems

1. LeetCode 20: Valid Parentheses

def isValid(s: str) -> bool:
    stack = []
    brackets = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in brackets.values():  # Opening bracket
            stack.append(char)
        else:  # Closing bracket
            if not stack or stack.pop() != brackets[char]:
                return False

    return len(stack) == 0

1. LeetCode 32: Longest Valid Parentheses
2. LeetCode 1249: Minimum Remove to Make Valid Parentheses

Category 2: Next Greater/Smaller Element

1. LeetCode 496: Next Greater Element I

def nextGreaterElement(nums1, nums2):
    stack = []
    next_greater = {}

    # Find next greater for all elements in nums2
    for num in nums2:
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        stack.append(num)

    # Fill remaining elements with -1
    while stack:
        next_greater[stack.pop()] = -1

    # Build result for nums1
    return [next_greater[num] for num in nums1]

1. LeetCode 503: Next Greater Element II (Circular Array)