When to Store Indices vs Values in Monotonic Stack

Do you need to calculate i - j (distance)?
├─ YES → Store indices
└─ NO → Continue

Do you need to access original array later?
├─ YES → Store indices
└─ NO → Store values (simpler)

def dailyTemperatures(temperatures):
    """
    Need distance: i - idx
    → Store indices
    """
    result = [0] * len(temperatures)
    stack = []  # Store indices
    
    for i in range(len(temperatures)):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            idx = stack.pop()
            result[idx] = i - idx  # Calculate distance!
        stack.append(i)
    
    return result

def trap(height):
    """
    Need to access height[stack[-1]] multiple times
    → Store indices
    """
    water = 0
    stack = []  # Store indices
    
    for i in range(len(height)):
        while stack and height[i] > height[stack[-1]]:
            bottom = stack.pop()
            if not stack:
                break
            
            # Access original array multiple times
            left_height = height[stack[-1]]
            right_height = height[i]
            bottom_height = height[bottom]
            
            width = i - stack[-1] - 1
            bounded_height = min(left_height, right_height) - bottom_height
            water += width * bounded_height
        
        stack.append(i)
    
    return water

class StockSpanner:
    def __init__(self):
        self.prices = []
        self.stack = []  # Store indices
    
    def next(self, price):
        self.prices.append(price)
        current_index = len(self.prices) - 1
        
        while self.stack and self.prices[self.stack[-1]] <= price:
            self.stack.pop()
        
        # Calculate span using indices
        if not self.stack:
            span = current_index + 1
        else:
            span = current_index - self.stack[-1]
        
        self.stack.append(current_index)
        return span

def removeKdigits(num, k):
    """
    Only need to compare digits
    → Store values (simpler)
    """
    stack = []  # Store values (characters)
    
    for digit in num:
        # Only comparing values, no distance needed
        while stack and k > 0 and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    
    # Remove remaining k digits
    if k > 0:
        stack = stack[:-k]
    
    result = ''.join(stack).lstrip('0')
    return result if result else '0'

def isValid(s):
    """
    Only need to match characters
    → Store values (simpler)
    """
    stack = []  # Store values (characters)
    pairs = {'(': ')', '[': ']', '{': '}'}
    
    for char in s:
        if char in pairs:
            stack.append(char)
        elif not stack or pairs[stack.pop()] != char:
            return False
    
    return not stack

┌─────────────────────────────────────────────────────────┐
│ STEP 1: Do you need distances (i - j)?                 │
├─────────────────────────────────────────────────────────┤
│ YES → Store indices                                     │
│ Examples: Daily Temperatures, Stock Span               │
└─────────────────────────────────────────────────────────┘
                        │
                        ↓ NO
┌─────────────────────────────────────────────────────────┐
│ STEP 2: Do you need to access original array?          │
├─────────────────────────────────────────────────────────┤
│ YES → Store indices                                     │
│ Examples: Trapping Rain Water, Histogram               │
└─────────────────────────────────────────────────────────┘
                        │
                        ↓ NO
┌─────────────────────────────────────────────────────────┐
│ STEP 3: Do you need position information?              │
├─────────────────────────────────────────────────────────┤
│ YES → Store indices                                     │
│ NO → Store values (simpler)                            │
│ Examples: Remove K Digits, Valid Parentheses           │
└─────────────────────────────────────────────────────────┘

# If you need this:
distance = i - idx  # Store indices

# If you only need this:
if value1 > value2:  # Store values