單調堆疊資料結構

def monotonic_stack_template(arr):
    """
    Universal template for monotonic stack problems
    Modify the condition and processing logic based on problem requirements
    """
    stack = []  # Store indices or values
    result = []
    
    for i, val in enumerate(arr):
        # Pop elements that violate monotonic property
        while stack and should_pop(stack, val, i):
            # Process the popped element
            popped = stack.pop()
            process_popped_element(popped, i, result)
        
        # Add current element to stack
        stack.append(i)  # or val depending on problem
    
    # Process remaining elements in stack
    while stack:
        popped = stack.pop()
        process_remaining_element(popped, result)
    
    return result

def should_pop(stack, current_val, current_idx):
    """Define when to pop based on problem requirements"""
    # For next greater: return arr[stack[-1]] <= current_val
    # For next smaller: return arr[stack[-1]] >= current_val
    pass

def process_popped_element(popped_idx, current_idx, result):
    """Process element when it's popped (found its next greater/smaller)"""
    pass

def process_remaining_element(popped_idx, result):
    """Process elements remaining in stack at the end"""
    pass

// Java Universal Template
public int[] monotonicStackTemplate(int[] arr) {
    Stack<Integer> stack = new Stack<>();
    int[] result = new int[arr.length];
    
    for (int i = 0; i < arr.length; i++) {
        // Pop elements that violate monotonic property
        while (!stack.isEmpty() && shouldPop(stack, arr, i)) {
            int poppedIdx = stack.pop();
            processElement(poppedIdx, i, result, arr);
        }
        
        // Add current element to stack
        stack.push(i);
    }
    
    // Process remaining elements
    while (!stack.isEmpty()) {
        int poppedIdx = stack.pop();
        processRemainingElement(poppedIdx, result);
    }
    
    return result;
}

private boolean shouldPop(Stack<Integer> stack, int[] arr, int currentIdx) {
    // Define condition based on problem requirements
    return arr[stack.peek()] <= arr[currentIdx]; // For next greater
}

def next_greater_element(nums):
    """
    Find next greater element for each element
    LC 496, LC 503, LC 739
    """
    n = len(nums)
    result = [-1] * n
    stack = []  # Store indices
    
    for i in range(n):
        # Pop smaller or equal elements
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]  # Found next greater
        
        stack.append(i)
    
    return result

// Java Template 1
public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Stack<Integer> stack = new Stack<>();
    
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    
    return result;
}

def next_smaller_element(nums):
    """
    Find next smaller element for each element
    Used in LC 84, LC 42
    """
    n = len(nums)
    result = [-1] * n
    stack = []  # Store indices
    
    for i in range(n):
        # Pop greater or equal elements
        while stack and nums[stack[-1]] > nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]  # Found next smaller
        
        stack.append(i)
    
    return result

def largest_rectangle_area(heights):
    """
    Find largest rectangle area in histogram
    LC 84, LC 85
    """
    stack = []  # Store indices
    max_area = 0
    
    # Sentinel 0 flushes every bar left on the stack; `heights + [0]` rather than
    # heights.append(0), so the caller's list is not mutated
    for i, h in enumerate(heights + [0]):
        # Pop taller bars and calculate area
        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)
    
    return max_area

// Java Template 3
public int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    int maxArea = 0;
    int n = heights.length;
    
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        
        while (!stack.isEmpty() && heights[stack.peek()] > h) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        
        stack.push(i);
    }
    
    return maxArea;
}

def next_greater_circular(nums):
    """
    Find next greater element in circular array
    LC 503
    """
    n = len(nums)
    result = [-1] * n
    stack = []
    
    # Process array twice to handle circular nature
    for i in range(2 * n):
        # Pop smaller elements
        while stack and nums[stack[-1]] < nums[i % n]:
            idx = stack.pop()
            result[idx] = nums[i % n]
        
        # Only add indices from first pass
        if i < n:
            stack.append(i)
    
    return result

def monotonic_stack_with_info(nums):
    """
    Store additional information with stack elements
    Used for complex calculations
    """
    stack = []  # Store (index, value, additional_info)
    result = []
    
    for i, val in enumerate(nums):
        while stack and stack[-1][1] <= val:
            idx, old_val, info = stack.pop()
            # Process with additional information
            result.append(calculate_result(idx, i, old_val, val, info))
        
        # Calculate additional information for current element
        additional_info = calculate_info(val, stack)
        stack.append((i, val, additional_info))
    
    return result

def find_132_pattern(nums):
    """
    Find 132 pattern in array
    LC 456
    """
    n = len(nums)
    if n < 3:
        return False
    
    stack = []  # Store potential k values (decreasing)
    second = float('-inf')  # The "2" in 132 pattern
    
    # Traverse from right to left
    for i in range(n - 1, -1, -1):
        if nums[i] < second:  # Found "1" < "2"
            return True
        
        # Pop smaller values and update second
        while stack and stack[-1] < nums[i]:
            second = stack.pop()
        
        stack.append(nums[i])
    
    return False

Problem Analysis for Monotonic Stack:

1. Does the problem involve finding next/previous elements?
   ├── YES: Next/Previous GREATER elements?
   │   ├── YES: Use Template 1 (Decreasing Stack)
   │   │   ├── Array is circular? → Use Template 4 (Circular)
   │   │   └── Standard case → Template 1
   │   └── NO: Next/Previous SMALLER elements?
   │       ├── YES: Use Template 2 (Increasing Stack)
   │       └── NO: Continue to step 2
   └── NO: Continue to step 2

2. Does the problem involve heights/areas/rectangles?
   ├── YES: Rectangle area calculation?
   │   ├── YES: Use Template 3 (Histogram)
   │   └── NO: Water trapping/volume?
   │       └── YES: Use Template 2 (Next Smaller)
   └── NO: Continue to step 3

3. Does the problem involve sequence validation/patterns?
   ├── YES: Parentheses/brackets?
   │   ├── YES: Use Template 5 (Validation)
   │   └── NO: Specific pattern (like 132)?
   │       └── YES: Use Template 6 (Pattern Detection)
   └── NO: Continue to step 4

4. Does the problem involve optimization/max-min constraints?
   ├── YES: Multiple criteria optimization?
   │   ├── YES: Use Template 5 (Complex Info)
   │   └── NO: Simple max/min tracking?
   │       └── YES: Use Template 1 or 2
   └── NO: Continue to step 5

5. Does the problem involve circular arrays or cyclic behavior?
   ├── YES: Use Template 4 (Circular Processing)
   └── NO: Consider if monotonic stack is the right approach
       └── May need different data structure/algorithm

# Standard next greater element
def next_greater_elements(nums):
    stack, result = [], [-1] * len(nums)
    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            result[stack.pop()] = num
        stack.append(i)
    return result

# Count contribution of each element
def sum_subarray_mins(arr):
    n = len(arr)
    left = [-1] * n    # Previous smaller element
    right = [n] * n    # Next smaller element
    
    # Calculate left boundaries
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    
    # Calculate contribution
    result = 0
    for i in range(n):
        result += arr[i] * (i - left[i]) * (right[i] - i)
    return result % (10**9 + 7)

# Largest rectangle with height as key
def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    for i, h in enumerate(heights + [0]):
        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)
    return max_area

// LC 739 - Daily Temperatures
// IDEA: Monotonic decreasing stack — pop when current > stack top
// time = O(N), space = O(N)
public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] ans = new int[n];
    Deque<Integer> stack = new ArrayDeque<>(); // stores indices
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop();
            ans[idx] = i - idx;
        }
        stack.push(i);
    }
    return ans;
}

// LC 84 - Largest Rectangle in Histogram
// IDEA: Monotonic increasing stack — pop and compute area on shorter bar
// time = O(N), space = O(N)
public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    int maxArea = 0;
    for (int i = 0; i <= heights.length; i++) {
        int h = (i == heights.length) ? 0 : heights[i];
        while (!stack.isEmpty() && h < heights[stack.peek()]) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

   left boundary  = previous SMALLER bar  -> the index just under it on the stack
   right boundary = next SMALLER bar      -> the index i that pops it

         left            popped            i
          |    >= h   [   h   ]   >= h     |
   width = i - stack[-1] - 1     (stack empty after the pop -> width = i)

# python
# LC 84 - Largest Rectangle in Histogram (two-phase: main loop + drain)
# IDEA: increasing stack of indices; a pop fixes the popped bar's height, the current
#       index is its right boundary, the new stack top is its left boundary
# time = O(n), space = O(n)
def largestRectangleArea(heights):
    stack, max_area, n = [], 0, len(heights)
    for i in range(n):
        while stack and heights[stack[-1]] > heights[i]:
            h = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, h * width)
        stack.append(i)
    # Drain: nothing shorter ever arrived on their right, so they extend to n
    while stack:
        h = heights[stack.pop()]
        width = n if not stack else n - stack[-1] - 1
        max_area = max(max_area, h * width)
    return max_area

i=0 h=2 : push                          stack=[0]
i=1 h=1 : pop 0 (h=2) left=-1 w=1  area=2   best=2
          push                          stack=[1]
i=2 h=5 : push                          stack=[1,2]
i=3 h=6 : push                          stack=[1,2,3]
i=4 h=2 : pop 3 (h=6) left=2  w=1  area=6   best=6
          pop 2 (h=5) left=1  w=2  area=10  best=10   <- bars 2..3 at height 5
          push                          stack=[1,4]
i=5 h=3 : push                          stack=[1,4,5]
i=6 end : pop 5 (h=3) left=4  w=1  area=3
          pop 4 (h=2) left=1  w=4  area=8
          pop 1 (h=1) left=-1 w=6  area=6   best=10

# python
# LC 84 - Largest Rectangle in Histogram ((start, height) stack)
# IDEA: stack entries are (leftmost index this height reaches, height), heights increasing;
#       a popped entry's rectangle is [start, i), and the popper inherits its start
# time = O(n), space = O(n)
def largestRectangleArea(heights):
    st, max_area = [], 0
    for i, h in enumerate(heights):
        start = i
        while st and st[-1][1] > h:
            start, prev_h = st.pop()
            max_area = max(max_area, prev_h * (i - start))
        st.append((start, h))
    n = len(heights)
    for start, h in st:              # survivors reach the right end
        max_area = max(max_area, h * (n - start))
    return max_area

// LC 496 - Next Greater Element I
// IDEA: Monotonic decreasing stack on nums2; store results in map
// time = O(M + N), space = O(M)
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<>(); // val -> next greater val
    Deque<Integer> stack = new ArrayDeque<>();
    for (int num : nums2) {
        while (!stack.isEmpty() && num > stack.peek()) {
            map.put(stack.pop(), num);
        }
        stack.push(num);
    }
    int[] ans = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        ans[i] = map.getOrDefault(nums1[i], -1);
    }
    return ans;
}

// LC 42 - Trapping Rain Water
// IDEA: Monotonic stack — pop when taller bar found, water fills between boundaries
// time = O(N), space = O(N)
public int trap(int[] height) {
    Deque<Integer> stack = new ArrayDeque<>();
    int water = 0;
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int bottom = stack.pop();
            if (stack.isEmpty()) break;
            int left = stack.peek();
            int width = i - left - 1;
            int boundedHeight = Math.min(height[left], height[i]) - height[bottom];
            water += width * boundedHeight;
        }
        stack.push(i);
    }
    return water;
}

// LC 503 - Next Greater Element II (circular array)
// IDEA: Monotonic stack — traverse 2n indices with modulo for circular effect
// time = O(N), space = O(N)
public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < 2 * n; i++) {
        while (!stack.isEmpty() && nums[i % n] > nums[stack.peek()]) {
            ans[stack.pop()] = nums[i % n];
        }
        if (i < n) stack.push(i);
    }
    return ans;
}

// LC 901 - Online Stock Span
// IDEA: Monotonic decreasing stack storing [price, span] pairs
// time = O(1) amortized per call, space = O(N)
class StockSpanner {
    Deque<int[]> stack = new ArrayDeque<>(); // [price, span]
    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }
        stack.push(new int[]{price, span});
        return span;
    }
}

// LC 907 - Sum of Subarray Minimums
// IDEA: Monotonic stack — for each element find left & right span as minimum
// time = O(N), space = O(N)
public int sumSubarrayMins(int[] arr) {
    int n = arr.length;
    int MOD = 1_000_000_007;
    int[] left = new int[n], right = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    // left[i] = distance to previous smaller element
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) stack.pop();
        left[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
        stack.push(i);
    }
    stack.clear();
    // right[i] = distance to next smaller or equal element
    for (int i = n-1; i >= 0; i--) {
        while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) stack.pop();
        right[i] = stack.isEmpty() ? n - i : stack.peek() - i;
        stack.push(i);
    }
    long ans = 0;
    for (int i = 0; i < n; i++) ans = (ans + (long) arr[i] * left[i] * right[i]) % MOD;
    return (int) ans;
}

        left choices              right choices
           <---->                    <----->
   ┌───────────────────────────────────────────────┐
   │  ...  PSE   .   .   .   [i]   .   .   .   NSE   │      arr
   └───────────────────────────────────────────────┘
              ^                          ^
        previous smaller           next smaller-or-equal
        element (strict >=)        element (strict >)

   left[i]  = i - PSE     ← # of left endpoints that keep arr[i] as min
   right[i] = NSE - i     ← # of right endpoints that keep arr[i] as min

   count(i) = left[i] * right[i]
   contribution = arr[i] * left[i] * right[i]

# python
# LC 907 - Sum of Subarray Minimums (contribution method)
# time = O(n), space = O(n)
MOD = 10**9 + 7
n = len(arr)
left  = [0] * n   # left[i]  = distance to previous smaller element
right = [0] * n   # right[i] = distance to next smaller-or-equal element

# --- LEFT pass: distance to Previous Smaller Element (pop on >=) ---
mono_st = []
for i in range(n):
    val = arr[i]
    # Pop elements that are greater than OR EQUAL to current val
    while mono_st and arr[mono_st[-1]] >= val:
        mono_st.pop()   # these can't be the left boundary of arr[i]

    # If stack empty -> val is the smallest so far, boundary is index -1
    #   left choices = i - (-1) = i + 1
    # Else -> boundary is the surviving stack top (the PSE)
    #   left choices = i - mono_st[-1]
    left[i] = i + 1 if not mono_st else i - mono_st[-1]
    mono_st.append(i)

# --- RIGHT pass: distance to Next Smaller Element (pop on >) ---
mono_st = []
for i in range(n - 1, -1, -1):
    val = arr[i]
    while mono_st and arr[mono_st[-1]] > val:   # strict > here
        mono_st.pop()
    right[i] = n - i if not mono_st else mono_st[-1] - i
    mono_st.append(i)

ans = 0
for i in range(n):
    ans = (ans + arr[i] * left[i] * right[i]) % MOD

i=0 val=3 : stack empty              -> left[0] = 0-(-1) = 1   stack=[0]
i=1 val=1 : arr[0]=3 >= 1 -> pop 0
            stack empty              -> left[1] = 1-(-1) = 2   stack=[1]
i=2 val=2 : arr[1]=1 >= 2? no        -> left[2] = 2-1     = 1   stack=[1,2]
i=3 val=4 : arr[2]=2 >= 4? no        -> left[3] = 3-2     = 1   stack=[1,2,3]

left  = [1, 2, 1, 1]
right = [1, 3, 2, 1]   (symmetric backward pass with strict >)

contribution = 3*1*1 + 1*2*3 + 2*1*2 + 4*1*1 = 3 + 6 + 4 + 4 = 17  ✓

// LC 402 - Remove K Digits
// IDEA: Greedy + monotonic increasing stack — remove larger digits greedily
// time = O(N), space = O(N)
public String removeKdigits(String num, int k) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : num.toCharArray()) {
        while (k > 0 && !stack.isEmpty() && stack.peek() > c) {
            stack.pop(); k--;
        }
        stack.push(c);
    }
    while (k-- > 0) stack.pop(); // remove from top if k still > 0
    // reconstruct result in correct order (bottom to top of stack)
    Deque<Character> result = new ArrayDeque<>(stack);
    StringBuilder sb = new StringBuilder();
    boolean leadingZero = true;
    while (!result.isEmpty()) {
        char c = result.pollFirst();
        if (leadingZero && c == '0') continue;
        leadingZero = false;
        sb.append(c);
    }
    return sb.length() == 0 ? "0" : sb.toString();
}

// LC 85 - Maximal Rectangle
// IDEA: For each row build histogram; apply largestRectangleArea (LC 84) logic
// time = O(M*N), space = O(N)
public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) return 0;
    int n = matrix[0].length, maxArea = 0;
    int[] heights = new int[n];
    for (char[] row : matrix) {
        for (int j = 0; j < n; j++)
            heights[j] = row[j] == '0' ? 0 : heights[j] + 1;
        maxArea = Math.max(maxArea, largestRectangle(heights));
    }
    return maxArea;
}
private int largestRectangle(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    int max = 0;
    for (int i = 0; i <= heights.length; i++) {
        int h = i == heights.length ? 0 : heights[i];
        while (!stack.isEmpty() && h < heights[stack.peek()]) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            max = Math.max(max, height * width);
        }
        stack.push(i);
    }
    return max;
}

nobody can pass the entity ahead of it
  -> you can only ever merge with the entity DIRECTLY ahead
  -> a merged group moves at the FRONT member's speed (the rear one slows down)

so: scan RIGHT -> LEFT (front -> back), and the survivors appear in order

t_i = (target - position[i]) / speed[i]

# python
# LC 853 - Car Fleet  (the textbook "stack" version)
# time = O(n log n), space = O(n)
def carFleet(target, position, speed):
    st = []
    for p, s in sorted(zip(position, speed), reverse=True):   # front -> back
        t = (target - p) / s
        if not st or t > st[-1]:      # cannot catch the fleet ahead -> new fleet
            st.append(t)
        # else: t <= st[-1], it catches up and is absorbed — nothing to record
    return len(st)

# python
# LC 853 - the same algorithm, stack removed
# time = O(n log n) (the sort), space = O(1)
def carFleet(target, position, speed):
    cnt, mx = 0, 0.0
    for p, s in sorted(zip(position, speed), reverse=True):   # front -> back
        t = (target - p) / s
        if t > mx:                    # arrives later than anyone ahead -> its own fleet
            cnt += 1
            mx = t
    return cnt

// java
// LC 853 - Car Fleet, running-max greedy
// time = O(N log N), space = O(N) for the index array (O(1) beyond the sort)
public int carFleet(int target, int[] position, int[] speed) {
    int n = position.length;
    Integer[] idx = new Integer[n];
    for (int i = 0; i < n; i++) idx[i] = i;
    Arrays.sort(idx, (a, b) -> position[b] - position[a]);   // front -> back
    int cnt = 0;
    double mx = 0.0;
    for (int i : idx) {
        double t = (double) (target - position[i]) / speed[i];
        if (t > mx) { cnt++; mx = t; }
    }
    return cnt;
}

position[i+1] - position[i] <= distance   -> already touching at t = 0
speed[i] > cur_s                          -> closing on the front group, and with
                                             infinite time ANY positive closing rate
                                             eventually eats ANY gap

# python
# LC 4045 - Count Robot Groups   (position is given sorted, so no sort is needed)
# IDEA: right -> left; `cur_s` is the speed of the frontmost group that survived.
# time = O(n), space = O(1)
def countGroups(position, speed, distance):
    n = len(position)
    cur_s = speed[n - 1]           # the frontmost robot is always a group on its own
    cnt = 1
    for i in range(n - 2, -1, -1):
        # touching test -> the NEIGHBOUR;  closing test -> the FRONT group
        if position[i + 1] - position[i] <= distance or speed[i] > cur_s:
            continue               # absorbed
        cnt += 1
        cur_s = speed[i]           # a new frontmost survivor
    return cnt

position = [18,19,22,24], distance = 3     gaps: 1, 3, 2  -> every pair touches
all four collapse at t = 0, even though 18 is 6 away from the group's position 24

if car i reaches car j LATER than j's own collision time
    -> j is already gone when i gets there
    -> i's real target is whatever is further ahead
    -> back up to an older candidate        <- THIS is a pop

# python
# LC 1776 - Car Fleet II: ans[i] = when car i collides with the car ahead (-1 = never)
# IDEA: right -> left monotonic stack of cars still catchable. Pop a candidate that
#       cannot be caught, or that dies before we reach it.
# time = O(n), space = O(n)
def getCollisionTimes(cars):
    n = len(cars)
    ans = [-1.0] * n
    st = []                                     # indices, front -> back
    for i in range(n - 1, -1, -1):
        p, s = cars[i]
        while st:
            j = st[-1]
            pj, sj = cars[j]
            # (a) not faster than j -> can never reach it
            # (b) reaching j takes longer than j survives -> aim further ahead
            if s <= sj or (ans[j] > 0 and (pj - p) / (s - sj) >= ans[j]):
                st.pop()
            else:
                break
        if st:
            j = st[-1]
            ans[i] = (cars[j][0] - p) / (s - cars[j][1])
        st.append(i)
    return ans

# cars = [[1,2],[2,1],[4,3],[7,2]] -> [1.0, -1.0, 3.0, -1.0]
# cars = [[3,4],[5,4],[6,3],[9,1]] -> [2.0, 1.0, 1.5, -1.0]

// LC 735 - Asteroid Collision
// IDEA: Stack — simulate collisions between right (+) and left (-) asteroids
// time = O(N), space = O(N)
public int[] asteroidCollision(int[] asteroids) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (int a : asteroids) {
        boolean alive = true;
        while (alive && a < 0 && !stack.isEmpty() && stack.peek() > 0) {
            if (stack.peek() < -a) { stack.pop(); }      // stack top destroyed
            else if (stack.peek() == -a) { stack.pop(); alive = false; } // both destroyed
            else alive = false;                             // incoming destroyed
        }
        if (alive) stack.push(a);
    }
    int[] res = new int[stack.size()];
    for (int i = res.length - 1; i >= 0; i--) res[i] = stack.pop();
    return res;
}

range(subarray) = max − min
sum(all ranges) = sum(all subarray maxs) − sum(all subarray mins)

count = (mid − L) × (R − mid)
contribution = nums[mid] × count

Decreasing stack (max contribution)

i=0: push 0         stack=[0]
i=1: nums[0]=1 < nums[1]=3 → pop mid=0
       left=-1, right=1
       contrib = 1 * (0-(-1)) * (1-0) = 1*1*1 = 1
     push 1          stack=[1]
i=2: nums[1]=3 > nums[2]=2, no pop
     push 2          stack=[1,2]
i=3 (sentinel): flush
     pop mid=2: left=1, right=3  → 2*(2-1)*(3-2) = 2
     pop mid=1: left=-1, right=3 → 3*(1-(-1))*(3-1) = 12

max_sum = 1 + 2 + 12 = 15

min pass (increasing stack) → min_sum = 10

answer = 15 − 10 = 5  ✓
verify: [1]=0,[3]=0,[2]=0,[1,3]=2,[3,2]=1,[1,3,2]=2 → sum = 5

# python
# LC 2104 - Sum of Subarray Ranges
# IDEA: sum(ranges) = sum(subarray maxs) - sum(subarray mins)
#       Contribution method via monotonic stack — one pass per role
# time = O(N), space = O(N)
def subArrayRanges(nums):
    n = len(nums)

    def contribution(is_max):
        stack = []
        total = 0
        for i in range(n + 1):          # sentinel: i == n flushes remaining
            while stack and (
                i == n or
                (nums[stack[-1]] < nums[i] if is_max else nums[stack[-1]] > nums[i])
            ):
                mid = stack.pop()
                left  = stack[-1] if stack else -1   # previous boundary index
                right = i                            # current index = right boundary
                total += nums[mid] * (mid - left) * (right - mid)
            stack.append(i)
        return total

    return contribution(True) - contribution(False)

// java
// LC 2104 - Sum of Subarray Ranges
// IDEA: sum(ranges) = sum(subarray maxs) - sum(subarray mins)
//       Contribution method: for each element count subarrays where it's max/min
// time = O(N), space = O(N)
public long subArrayRanges(int[] nums) {
    return contribution(nums, true) - contribution(nums, false);
}

private long contribution(int[] nums, boolean isMax) {
    int n = nums.length;
    Deque<Integer> stack = new ArrayDeque<>();
    long total = 0;

    for (int i = 0; i <= n; i++) {          // i == n is the sentinel flush
        while (!stack.isEmpty()) {
            int mid = stack.peek();
            boolean shouldPop = (i == n) ||
                (isMax ? nums[mid] < nums[i] : nums[mid] > nums[i]);
            if (!shouldPop) break;
            stack.pop();
            int left  = stack.isEmpty() ? -1 : stack.peek(); // prev boundary
            int right = i;                                    // next boundary
            total += (long) nums[mid] * (mid - left) * (right - mid);
        }
        stack.push(i);
    }
    return total;
}

"dir\n\tsub1\n\t\tfile.ext\n\tsub2"

line          depth   pop until size==depth   stack (path lengths, '/' included)
dir             0     []                      [4]            "dir/"
  sub1          1     [4]                     [4, 9]         "dir/sub1/"
    file.ext    2     [4, 9]                  (file → no push, len = 9 + 8 = 17)
  sub2          1     pop 9 → [4]             [4, 9]

// java
// LC 388 - Longest Absolute File Path
// IDEA: Stack indexed by nesting depth — stack.peek() = length of the current
//       directory prefix (with trailing '/'); pop until size == depth to leave sibling branches
// time = O(N), space = O(D)  // N = input length, D = max depth
public int lengthLongestPath(String input) {
    Deque<Integer> stack = new ArrayDeque<>(); // prefix length per depth
    int maxLen = 0;
    for (String line : input.split("\n")) {
        int depth = line.lastIndexOf('\t') + 1;  // tabs are leading & contiguous
        String name = line.substring(depth);
        while (stack.size() > depth) stack.pop();          // leave finished branches
        int parentLen = stack.isEmpty() ? 0 : stack.peek();
        int curLen = parentLen + name.length();
        if (name.indexOf('.') >= 0) {
            maxLen = Math.max(maxLen, curLen);             // file → candidate answer
        } else {
            stack.push(curLen + 1);                        // dir → +1 for '/'
        }
    }
    return maxLen;
}

# python
# LC 388 - Longest Absolute File Path
# IDEA: stack[d] = length of the directory prefix at depth d (trailing '/' counted);
#       pop until len(stack) == depth so sibling branches are discarded
# time = O(N), space = O(D)
def lengthLongestPath(input: str) -> int:
    stack = []          # prefix length per depth
    best = 0
    for line in input.split('\n'):
        depth = len(line) - len(line.lstrip('\t'))
        name = line[depth:]
        while len(stack) > depth:
            stack.pop()
        parent = stack[-1] if stack else 0
        cur = parent + len(name)
        if '.' in name:
            best = max(best, cur)      # file
        else:
            stack.append(cur + 1)      # dir, +1 for '/'
    return best

pop, then:
  stack empty  → this ')' is unmatched → push i as the NEW base
  stack !empty → length = i - stack.top()

i=0 ')'  pop -1 → empty → push 0        stack=[0]        best=0
i=1 '('  push 1                          stack=[0,1]
i=2 ')'  pop 1 → top=0 → 2-0 = 2         stack=[0]        best=2
i=3 '('  push 3                          stack=[0,3]
i=4 ')'  pop 3 → top=0 → 4-0 = 4         stack=[0]        best=4
i=5 ')'  pop 0 → empty → push 5          stack=[5]        best=4  ✓

// java
// LC 32 - Longest Valid Parentheses
// IDEA: Stack of indices seeded with -1 (base). On ')' pop; if empty this ')' becomes
//       the new base, else answer candidate = i - stack.peek()
// time = O(N), space = O(N)
public int longestValidParentheses(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1);                 // base = index before the current valid block
    int best = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.isEmpty()) stack.push(i);                 // unmatched ')' → new base
            else best = Math.max(best, i - stack.peek());
        }
    }
    return best;
}

# python
# LC 32 - Longest Valid Parentheses
# IDEA: index stack with -1 sentinel; i - stack[-1] = length of valid run ending at i
# time = O(N), space = O(N)
def longestValidParentheses(s: str) -> int:
    stack = [-1]          # base index
    best = 0
    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)               # new base
            else:
                best = max(best, i - stack[-1])
    return best

nums = [3,2,1,6,0,5]

3 → stack[3]
2 → 3>2, 3.right = 2            stack[3,2]
1 → 2>1, 2.right = 1            stack[3,2,1]
6 → pop 1,2,3 (each becomes 6.left in turn, last popped wins) → stack empty
                                 stack[6]      root = 6
0 → 6.right = 0                 stack[6,0]
5 → pop 0 → 5.left = 0; top 6 → 6.right = 5   stack[6,5]

// java
// LC 654 - Maximum Binary Tree
// IDEA: Monotonic DECREASING stack of nodes. Nodes popped by num become num's left
//       subtree (last popped = direct left child); surviving top adopts num as right child
// time = O(N), space = O(N)   // beats the O(N^2) divide & conquer build
public TreeNode constructMaximumBinaryTree(int[] nums) {
    Deque<TreeNode> stack = new ArrayDeque<>(); // values decreasing: bottom -> top
    for (int num : nums) {
        TreeNode cur = new TreeNode(num);
        while (!stack.isEmpty() && stack.peek().val < num) {
            cur.left = stack.pop();          // last popped ends up as the left child
        }
        if (!stack.isEmpty()) stack.peek().right = cur;
        stack.push(cur);
    }
    return stack.isEmpty() ? null : stack.peekLast(); // bottom of stack = global max = root
}

# python
# LC 654 - Maximum Binary Tree
# IDEA: monotonic decreasing stack of nodes; popped nodes chain into cur.left,
#       remaining top takes cur as its right child; stack[0] is the root
# time = O(N), space = O(N)
def constructMaximumBinaryTree(nums):
    stack = []                      # node values decreasing
    for num in nums:
        cur = TreeNode(num)
        while stack and stack[-1].val < num:
            cur.left = stack.pop()  # overwritten each pop -> keeps the LAST popped
        if stack:
            stack[-1].right = cur
        stack.append(cur)
    return stack[0] if stack else None

// java
// LC 155 - Min Stack
// IDEA: second stack keeps a non-increasing sequence of minima; push a new min when
//       val <= current min (the '=' is REQUIRED so duplicates survive matching pops)
// time = O(1) per op, space = O(N)
class MinStack {
    private final Deque<Integer> stack = new ArrayDeque<>();
    private final Deque<Integer> mins  = new ArrayDeque<>(); // non-increasing

    public void push(int val) {
        stack.push(val);
        if (mins.isEmpty() || val <= mins.peek()) mins.push(val);
    }
    public void pop() {
        int v = stack.pop();
        if (v == mins.peek()) mins.pop();
    }
    public int top()    { return stack.peek(); }
    public int getMin() { return mins.peek(); }
}

# python
# LC 155 - Min Stack
# IDEA: auxiliary non-increasing stack of minima; '<=' on push keeps duplicate minima
# time = O(1) per op, space = O(N)
class MinStack:
    def __init__(self):
        self.stack = []
        self.mins  = []          # non-increasing

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.mins or val <= self.mins[-1]:
            self.mins.append(val)

    def pop(self) -> None:
        if self.stack.pop() == self.mins[-1]:
            self.mins.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.mins[-1]

// java
// LC 768 - Max Chunks To Make Sorted II
// IDEA: monotonic increasing stack of chunk MAXIMA. A value smaller than the top must
//       merge every chunk it is smaller than; the merged chunk keeps the largest max
// time = O(N), space = O(N)
public int maxChunksToSorted(int[] arr) {
    Deque<Integer> stack = new ArrayDeque<>(); // chunk maxima, increasing bottom -> top
    for (int num : arr) {
        if (!stack.isEmpty() && num < stack.peek()) {
            int maxOfMerged = stack.pop();
            while (!stack.isEmpty() && num < stack.peek()) stack.pop();
            stack.push(maxOfMerged);           // merged chunk keeps the old max
        } else {
            stack.push(num);                   // starts a new chunk
        }
    }
    return stack.size();
}

# python
# LC 768 - Max Chunks To Make Sorted II
# IDEA: increasing stack of chunk maxima; merging keeps the largest max
# time = O(N), space = O(N)
def maxChunksToSorted(arr):
    stack = []                       # chunk maxima, increasing
    for num in arr:
        if stack and num < stack[-1]:
            merged_max = stack.pop()
            while stack and num < stack[-1]:
                stack.pop()
            stack.append(merged_max)
        else:
            stack.append(num)
    return len(stack)

# LC 769 - Max Chunks To Make Sorted (values are a permutation of 0..n-1)
# time = O(N), space = O(1)
def maxChunksToSortedI(arr):
    chunks, running_max = 0, -1
    for i, num in enumerate(arr):
        running_max = max(running_max, num)
        if running_max == i:         # prefix holds exactly the values 0..i
            chunks += 1
    return chunks

dp[i] = the round in which nums[i] is deleted     (0 = never deleted)
answer = max(dp)

keep a DECREASING stack of indices, then for each i:

  while nums[i] >= nums[stack[-1]]:        # this top can never kill me
      cur = max(cur, dp[stack.pop()])      #   -> inherit its deadline

  if stack:      dp[i] = cur + 1           # top is > nums[i]: my killer.
                                           #   it reaches me one round after
                                           #   the last of the popped ones died
  else:          dp[i] = 0                 # nothing bigger on the left -> I survive

stack = [ [val, steps_to_remove], ... ]

val             = the element's value
steps_to_remove = WHICH ROUND this element is deleted in   (0 = never)

i  nums[i]  pops (dp inherited)          stack after       dp[i]                 res
0    5      -                            [0]               0   (nothing bigger)   0
1    3      none (3 < 5)                 [0,1]             0+1 = 1                1
2    4      pop 1 -> cur=max(0,dp1)=1    [0,2]             1+1 = 2                2
3    4      pop 2 -> cur=max(0,dp2)=2    [0,3]             2+1 = 3                3
4    7      pop 3 (cur=3), pop 0         [4]               0   (stack emptied)     3

dp = [0,1,2,3,0]  ->  answer 3
check: round1 deletes 3 -> [5,4,4,7]; round2 deletes the first 4 -> [5,4,7];
       round3 deletes the second 4 -> [5,7]  ✓

idx     0  1  2  3  4  5  6  7  8  9 10
nums    5  3  4  4  7  3  6 11  8  5 11
steps   0  1  2  3  0  1  2  0  1  1  0
                                          <- every nonzero entry is a scheduled funeral

round 1  deletes steps==1  -> idx 1,5,8,9  (3, 3, 8, 5)
         [5,3,4,4,7,3,6,11,8,5,11] -> [5,4,4,7,6,11,11]

round 2  deletes steps==2  -> idx 2,6      (the first 4, and 6)
         [5,4,4,7,6,11,11] -> [5,4,7,11,11]

round 3  deletes steps==3  -> idx 3        (the second 4)
         [5,4,7,11,11] -> [5,7,11,11]      non-decreasing, stop

3 rounds  ==  max(steps)   ✓

nums = [5,3,4,4,7]
pop on >=  ->  dp = [0,1,2,3,0]  ->  3   ✓
pop on >   ->  dp = [0,1,2,1,0]  ->  2   ✗   (idx 3 wrongly adopts idx 2 as its killer)

# python
# LC 2289 - Steps to Make Array Non-decreasing
# IDEA: monotonic DECREASING stack of indices; dp[i] = round in which nums[i] dies.
#       A popped element hands its dp up: dp[i] = max(popped dp) + 1
# time = O(n), space = O(n)
def totalSteps(nums):
    n = len(nums)
    dp = [0] * n          # dp[i] = round nums[i] is removed (0 = never)
    stack = []            # indices, values monotonically DECREASING
    res = 0

    for i in range(n):
        cur = 0
        # NOTE !!! `>=` — an equal element is never deleted, so it is not a killer
        while stack and nums[i] >= nums[stack[-1]]:
            cur = max(cur, dp[stack.pop()])
        if stack:                       # a strictly greater element on the left = my killer
            dp[i] = cur + 1
            res = max(res, dp[i])
        stack.append(i)                 # else dp[i] stays 0: never removed

    return res

# python
# LC 2289 - variant: right -> left, steps = max(steps + 1, dp[j])
# time = O(n), space = O(n)
def totalSteps_rtl(nums):
    n = len(nums)
    dp = [0] * n
    stack, res = [], 0
    for i in range(n - 1, -1, -1):
        steps = 0
        while stack and nums[i] > nums[stack[-1]]:   # strict: only what I eat
            # one more round than eaten so far, but j may itself be dying until dp[j]
            steps = max(steps + 1, dp[stack.pop()])
        dp[i] = steps
        res = max(res, steps)
        stack.append(i)
    return res

// java
// LC 2289 - Steps to Make Array Non-decreasing
// IDEA: decreasing stack of indices; dp[i] = round nums[i] is removed.
//       dp[i] = max(dp of popped) + 1 when a strictly greater element remains on the left
// time = O(N), space = O(N)
public int totalSteps(int[] nums) {
    int n = nums.length, res = 0;
    int[] dp = new int[n];                          // dp[i] = round nums[i] dies (0 = never)
    Deque<Integer> stack = new ArrayDeque<>();      // indices, values decreasing

    for (int i = 0; i < n; i++) {
        int cur = 0;
        while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
            cur = Math.max(cur, dp[stack.pop()]);   // inherit the deadline
        }
        if (!stack.isEmpty()) {
            dp[i] = cur + 1;
            res = Math.max(res, dp[i]);
        }
        stack.push(i);
    }
    return res;
}

pairs(i) = (nxt[i] - i - 1)  -  #{ j in (i, nxt[i]) : nums[j] == nums[i] }
            window size          the equal-value chain

eq[i] = 1 + eq[ne]      if ne < nxt[i]
      = 0               otherwise

i=4  v=7   stack []        -> nxt=5  eq=0   pairs = (5-4-1) - 0 = 0
i=3  v=6   pop 7 (>= 6)    -> nxt=5  eq=0   pairs = (5-3-1) - 0 = 1   (3,4)
i=2  v=6   pop 6 (>= 6)    -> nxt=5  eq=1   pairs = (5-2-1) - 1 = 1   (2,4)
                idx 3 is equal and inside the window -> eq = 1 + eq[3] = 1
i=1  v=7   top 6 stays     -> nxt=2  eq=0   pairs = (2-1-1) - 0 = 0
i=0  v=6   pop 7, pop 6    -> nxt=5  eq=2   pairs = (5-0-1) - 2 = 2   (0,1) (0,4)
                idx 2 is equal and inside the window -> eq = 1 + eq[2] = 2
                                                              total  = 4

# python
# LC 4054 - Count Shadow Pairs I
# IDEA: nxt[i] = next STRICTLY smaller (so the stack pops on >=); every j in
#       (i, nxt[i]) is a candidate, less the ones equal to nums[i], which chain
# time = O(n), space = O(n)
def shadowPairs(nums):
    n = len(nums)
    nxt = [n] * n            # first idx > i whose value is strictly smaller
    eq = [0] * n             # how many nums[j] == nums[i] sit inside (i, nxt[i])
    last_same = {}           # value -> the smallest idx > i seen so far
    stack = []               # indices, values increasing towards the top
    res = 0

    # right -> left, so the stack already holds everything after i
    for i in range(n - 1, -1, -1):
        while stack and nums[stack[-1]] >= nums[i]:    # NOTE: >= , not >
            stack.pop()
        nxt[i] = stack[-1] if stack else n

        ne = last_same.get(nums[i], n)
        eq[i] = 1 + eq[ne] if ne < nxt[i] else 0

        res += (nxt[i] - i - 1) - eq[i]

        stack.append(i)
        last_same[nums[i]] = i

    return res

// java
// LC 4054 - Count Shadow Pairs I
// IDEA: the same nxt[] / eq[] pass, right -> left. NOTE the return type: the
//       count reaches ~5e9 on a strictly increasing array, so int overflows
// time = O(n), space = O(n)
public long shadowPairs(int[] nums) {
    int n = nums.length;
    int[] nxt = new int[n];                    // first idx > i with a strictly smaller value
    int[] eq = new int[n];                     // equal values sitting inside (i, nxt[i])
    Map<Integer, Integer> lastSame = new HashMap<>();
    Deque<Integer> stack = new ArrayDeque<>(); // indices, values increasing towards the top
    long res = 0;

    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) stack.pop();   // >= , not >
        nxt[i] = stack.isEmpty() ? n : stack.peek();

        int ne = lastSame.getOrDefault(nums[i], n);
        eq[i] = ne < nxt[i] ? 1 + eq[ne] : 0;

        res += (nxt[i] - i - 1) - eq[i];

        stack.push(i);
        lastSame.put(nums[i], i);
    }
    return res;
}

# python
# LC 4054 - Count Shadow Pairs I
# IDEA: stack of [value, freq] groups, increasing, plus `total` = sum of freqs.
#       Anything > x is dead the moment x arrives; whatever is left is <= x, so x
#       closes `total` pairs, less its own equal group (the pair test is strict)
# time = O(n), space = O(k)   k = distinct surviving values
def shadowPairs(nums):
    stack = []               # [value, freq], values strictly increasing
    total = 0                # live candidates = sum of the freqs on the stack
    cnt = 0

    for x in nums:
        while stack and stack[-1][0] > x:      # NOTE: > here — the equals must stay
            total -= stack.pop()[1]

        if stack and stack[-1][0] == x:
            cnt += total - stack[-1][1]        # skip its own group: needs a strict <
            stack[-1][1] += 1
        else:
            cnt += total                       # everything left is strictly smaller
            stack.append([x, 1])

        total += 1

    return cnt