堆疊（Stack）

// Java
Stack<Integer> stack = new Stack<>();
stack.push(element);  // O(1)

# Python
stack = []
stack.append(element)  # O(1)

// Java
int top = stack.pop();  // O(1), throws if empty

# Python
top = stack.pop()  # O(1), raises if empty

// Java
int top = stack.peek();  // O(1), throws if empty
if (!stack.isEmpty()) {
    top = stack.peek();
}

# Python
top = stack[-1]  # O(1), raises if empty
if stack:
    top = stack[-1]

Core Idea:
  - Opener  -> push it (we owe a matching closer)
  - Closer  -> stack must be non-empty AND top must be the matching opener
               (else fail fast)
  - End     -> stack must be EMPTY (no unmatched openers left)

When to Use:
  - Validate / repair / measure balanced sequences
  - Any "nesting must be well-formed" check (brackets, tags, expressions)

Counter vs Stack (interview discriminator):
  - ONE bracket type only  -> a running balance counter is enough, O(1) space
                              (LC 921, LC 1541, LC 1614)
  - MULTIPLE bracket types -> MUST use a stack (LC 20)
  - Need the POSITION of the offending bracket -> stack of INDICES
                              (LC 1249, LC 32)

Similar LC:
  - LC 20    Valid Parentheses                        (base template)
  - LC 1249  Minimum Remove to Make Valid Parentheses (stack of indices -> delete;
                                                    also two counter scans, no stack)
  - LC 921   Minimum Add to Make Parentheses Valid    (balance counter)
  - LC 32    Longest Valid Parentheses                (index stack + `-1` base;
                                                    also 1D DP, or two counter scans for O(1) space)
  - LC 856   Score of Parentheses                     (stack of partial scores)
  - LC 1541  Minimum Insertions to Balance a Parentheses String  ( `(` needs `))` )
  - LC 1614  Maximum Nesting Depth of the Parentheses (max depth = max balance)

// java
// LC 20 - Valid Parentheses
// IDEA: STACK — push openers, pop-and-verify on closers, stack must end empty
// time = O(n), space = O(n)
public boolean isValid(String s) {

    // closer -> its matching opener
    Map<Character, Character> pairs = new HashMap<>();
    pairs.put(')', '(');
    pairs.put(']', '[');
    pairs.put('}', '{');

    Deque<Character> st = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        if (pairs.containsKey(c)) {
            /**
             *  NOTE !!!  a closer needs BOTH checks:
             *   1) stack NOT empty  (e.g. ")" alone)
             *   2) top is the matching opener (e.g. "(]" must fail)
             *
             *  NOTE !!! unbox to `char` before comparing —
             *  comparing two Character objects with `!=` compares REFERENCES.
             */
            if (st.isEmpty()) {
                return false;
            }
            char top = st.pop();
            if (top != pairs.get(c)) {
                return false;
            }
        } else {
            st.push(c);
        }
    }

    /** NOTE !!! leftover openers => invalid (e.g. "(((") */
    return st.isEmpty();
}

# python
# LC 20 - Valid Parentheses
# IDEA: STACK — push openers, pop-and-verify on closers, stack must end empty
# time = O(n), space = O(n)
class Solution(object):
    def isValid(self, s):
        pairs = {')': '(', ']': '[', '}': '{'}
        stack = []
        for c in s:
            # closer
            if c in pairs:
                # NOTE !!! empty stack OR wrong partner -> invalid
                if not stack or stack.pop() != pairs[c]:
                    return False
            # opener
            else:
                stack.append(c)
        # NOTE !!! leftover openers -> invalid
        return not stack

# python
# LC 1249 - Minimum Remove to Make Valid Parentheses
# IDEA: STACK OF '(' INDICES — blank out unmatched ')' on sight, unmatched '(' after the scan
# time = O(n), space = O(n)
class Solution(object):
    def minRemoveToMakeValid(self, s):
        chars = list(s)      # mutable copy, so a position can be blanked in O(1)
        open_idx = []        # indices of '(' still waiting for a ')'

        for i in range(len(chars)):
            if chars[i] == '(':
                open_idx.append(i)
            elif chars[i] == ')':
                if open_idx:
                    open_idx.pop()     # matched -> keep both
                else:
                    chars[i] = ''      # NOTE !!! no '(' open before it -> can never match
            # letters never affect the balance

        # NOTE !!! the second flush: what is left on the stack are unmatched '('
        for i in open_idx:
            chars[i] = ''

        return ''.join(chars)  # '' entries vanish in the join

s = "a)b(c)d"

i  ch   action                          open_idx   chars
0  a    letter                          []         a ) b ( c ) d
1  )    stack empty -> blank index 1    []         a _ b ( c ) d
2  b    letter                          []
3  (    push 3                          [3]
4  c    letter                          [3]
5  )    pop 3 (matched)                 []
6  d    letter                          []
end     nothing left to flush                      -> "ab(c)d"

s = "))(("   ->  ')' x2 blanked on sight, '(' x2 left on the stack and flushed  ->  ""

# python
# LC 739, LC 503 - Find next `big number`
# ...
stack = [] # [[idx, val]]
for i, val in enumerate(tmp):
    while stack and stack[-1][1] < val:
        _idx, _val = stack.pop(-1)
        res[tmp[_idx]] = i - _idx
    stack.append([i, val]) 
# ...

// java
// LC 239
// LC 496
// ...

// Traverse the array from right to left
for (int i = 0; i < n; i++) {
    // Maintain a decreasing monotonic stack
    /** NOTE !!! below */
    while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
        stack.pop();  // Pop elements from the stack that are smaller or equal to the current element
    }
    
    // If stack is not empty, the next greater element is at the top of the stack
    if (!stack.isEmpty()) {
        result[i] = nums[stack.peek()];
    }
    
    // Push the current element's index onto the stack
    stack.push(i);
}

// ...

Invariant:  min_values[i] = min(stack[0], stack[1], ..., stack[i])
            -> min_values is NOT the elements sorted; it is a STATE per layer

push(v):    min_values.append(min(v, min_values[-1]))   # new layer, new state
pop():      min_values.pop()                             # the popped layer's state goes with it
getMin():   min_values[-1]                               # the top layer's state IS the answer

push -2, 0, -3        then pop()
  stack      = [-2,  0, -3]      stack      = [-2,  0]
  min_values = [-2, -2, -3]      min_values = [-2, -2]   <- getMin() = -2, nothing recomputed
                  ^    ^    ^
                  |    |    min of all three
                  |    min of the first two (0 did not beat -2)
                  min of the first one

# LC 155. Min Stack
# V0
# IDEA: 2 ARRAYS — stack holds the elements, min_values holds each layer's minimum
# time = O(1) per operation, space = O(n)
class MinStack(object):

    def __init__(self):
        self.stack = []
        # min_values[i] == min(stack[0..i]) — a STATE per layer, not the elements sorted
        self.min_values = []

    def push(self, val):
        self.stack.append(val)
        if not self.min_values:
            self.min_values.append(val)
        else:
            self.min_values.append(min(val, self.min_values[-1]))

    def pop(self):
        # the popped layer's state leaves with it — no comparison needed
        self.min_values.pop()
        return self.stack.pop()

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

    def getMin(self):
        # the top layer's state IS the current minimum — O(1)
        return self.min_values[-1]

# V1: the same invariant in one stack of (value, min_so_far) tuples
# time = O(1) per operation, space = O(n)
class MinStack(object):

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

    def push(self, x):
        if not self.stack:
            self.stack.append((x, x))
        else:
            self.stack.append((x, min(x, self.stack[-1][1])))

    def pop(self):
        self.stack.pop()

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

    def getMin(self):
        return self.stack[-1][1]

# LC 239 (as a min queue) / LC 1438 - a queue built from two min stacks
# IDEA: a queue is two stacks (LC 232). Give each stack its per-layer min and the
#       queue's min is the smaller of the two tops — no monotonic deque needed.
#       Swap min -> max for LC 239 itself; run one of each for LC 1438.
# time = O(1) amortised per operation, space = O(n)
class MinQueue(object):

    def __init__(self):
        self.inbox, self.outbox = [], []      # each entry: (value, min_so_far)

    @staticmethod
    def _push(st, v):
        st.append((v, v if not st else min(v, st[-1][1])))

    def push(self, v):
        self._push(self.inbox, v)

    def pop(self):
        if not self.outbox:                   # refill: each element moves once
            while self.inbox:
                self._push(self.outbox, self.inbox.pop()[0])
        return self.outbox.pop()[0]

    def getMin(self):
        return min(st[-1][1] for st in (self.inbox, self.outbox) if st)

# LC 1026 - Maximum Difference Between Node and Ancestor
# IDEA: the recursion stack IS the stack; (lo, hi) is that layer's aggregate over the
#       root-to-node path. Returning from the call pops it — no bookkeeping at all.
# time = O(n), space = O(h)
def maxAncestorDiff(root):
    def dfs(node, lo, hi):
        if not node:
            return hi - lo
        lo, hi = min(lo, node.val), max(hi, node.val)
        return max(dfs(node.left, lo, hi), dfs(node.right, lo, hi))
    return dfs(root, root.val, root.val)

# python
# LC 144 - Binary Tree Preorder Traversal
# IDEA: EXPLICIT STACK — push RIGHT before LEFT so LEFT is popped first
# time = O(n), space = O(h)
class Solution(object):
    def preorderTraversal(self, root):
        if not root:
            return []
        res, stack = [], [root]
        while stack:
            node = stack.pop()
            res.append(node.val)
            # NOTE !!! right first -> left ends up on TOP
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res


# LC 145 - Binary Tree Postorder Traversal
# IDEA: preorder variant (root -> RIGHT -> LEFT), then REVERSE => left-right-root
# time = O(n), space = O(h)
class Solution(object):
    def postorderTraversal(self, root):
        if not root:
            return []
        res, stack = [], [root]
        while stack:
            node = stack.pop()
            res.append(node.val)
            # NOTE !!! mirrored order compared with preorder
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return res[::-1]   # root-right-left  ->  left-right-root

// java
// LC 144 - Binary Tree Preorder Traversal
// IDEA: EXPLICIT STACK — push RIGHT before LEFT so LEFT is popped first
// time = O(n), space = O(h)
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    Deque<TreeNode> st = new ArrayDeque<>();
    st.push(root);
    while (!st.isEmpty()) {
        TreeNode node = st.pop();
        res.add(node.val);
        /** NOTE !!! right pushed FIRST, so left is popped FIRST */
        if (node.right != null) {
            st.push(node.right);
        }
        if (node.left != null) {
            st.push(node.left);
        }
    }
    return res;
}

// LC 145 - Binary Tree Postorder Traversal
// IDEA: preorder with LEFT/RIGHT swapped (root-right-left), then REVERSE
// time = O(n), space = O(h)
public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>();
    if (root == null) {
        return res;
    }
    Deque<TreeNode> st = new ArrayDeque<>();
    st.push(root);
    while (!st.isEmpty()) {
        TreeNode node = st.pop();
        /** NOTE !!! addFirst == "append then reverse", done incrementally */
        res.addFirst(node.val);
        if (node.left != null) {
            st.push(node.left);
        }
        if (node.right != null) {
            st.push(node.right);
        }
    }
    return res;
}

Core Idea:
  - Stack index == NESTING DEPTH. stack[d] = accumulated context at depth d.
  - On entering depth d : trim the stack down to d, then push the new context
  - On leaving  a scope : pop, and hand the accumulated value back to the parent
  - The parent is ALWAYS stack[-1] — that is what makes it a stack problem

When to Use:
  - Indented / tab-delimited input   -> depth = number of leading tabs (LC 388)
  - start/end (or open/close) events -> the "running" item is the stack top (LC 636)
  - Any "who is my parent?" question during a single left-to-right scan

Similar LC:
  - LC 388  Longest Absolute File Path       (depth-indexed prefix lengths)
  - LC 636  Exclusive Time of Functions      (running function = stack top)
  - LC 591  Tag Validator                    (open-tag stack + scope rules)
  - LC 71   Simplify Path                    (stack_examples.md; ".." pops the parent dir)

// java
// LC 388 - Longest Absolute File Path
// IDEA: SCOPE STACK indexed by DEPTH — stack.get(d) = length of the path prefix at depth d
// time = O(n), space = O(depth)
public int lengthLongestPath(String input) {

    int res = 0;

    /**
     *  NOTE !!!
     *   stack.get(d) = length of "dir1/dir2/.../" for the current branch at depth d
     *   (already includes the trailing '/')
     *   -> index in the list IS the nesting depth
     */
    List<Integer> stack = new ArrayList<>();
    stack.add(0); // depth 0 has an empty prefix

    for (String line : input.split("\n")) {

        // depth = number of leading '\t'
        int depth = 0;
        while (depth < line.length() && line.charAt(depth) == '\t') {
            depth++;
        }
        String name = line.substring(depth);

        /** NOTE !!! we LEFT the previous deeper scopes -> pop back to `depth` */
        while (stack.size() > depth + 1) {
            stack.remove(stack.size() - 1);
        }

        if (name.contains(".")) {
            // a FILE never becomes a parent -> just measure it
            res = Math.max(res, stack.get(depth) + name.length());
        } else {
            // a DIRECTORY becomes the context of depth+1 (+1 for the '/')
            stack.add(stack.get(depth) + name.length() + 1);
        }
    }

    return res;
}

# python
# LC 388 - Longest Absolute File Path
# IDEA: SCOPE STACK indexed by DEPTH — stack[d] = length of the path prefix at depth d
# time = O(n), space = O(depth)
class Solution(object):
    def lengthLongestPath(self, input):
        res = 0
        stack = [0]   # stack[d] = prefix length at depth d (trailing '/' included)

        for line in input.split('\n'):
            name = line.lstrip('\t')
            depth = len(line) - len(name)   # number of leading tabs

            # NOTE !!! we left deeper scopes -> trim the stack back to this depth
            while len(stack) > depth + 1:
                stack.pop()

            if '.' in name:
                # file: measure, never push (a file has no children)
                res = max(res, stack[depth] + len(name))
            else:
                # dir: becomes the prefix for depth+1, +1 for the '/'
                stack.append(stack[depth] + len(name) + 1)

        return res

# Trace: "dir\n\tsubdir2\n\t\tfile.ext"
#   "dir"        d=0 -> stack = [0, 4]           ("dir/")
#   "subdir2"    d=1 -> stack = [0, 4, 12]       ("dir/subdir2/")
#   "file.ext"   d=2 -> res = 12 + 8 = 20

// java
// LC 388 - Longest Absolute File Path
// IDEA: HASH MAP by DEPTH — pathLen[d] = prefix length for children at depth d; overwrite, never pop
// time = O(n), space = O(depth)
public int lengthLongestPath(String input) {
    int res = 0;
    Map<Integer, Integer> pathLen = new HashMap<>();
    pathLen.put(0, 0); // depth-0 entries have an empty prefix

    for (String line : input.split("\n")) {
        int depth = line.lastIndexOf('\t') + 1;   // tabs are leading and contiguous
        String name = line.substring(depth);

        if (name.contains(".")) {
            res = Math.max(res, pathLen.get(depth) + name.length());
        } else {
            // NOTE !!! overwrite the slot for depth+1 — any stale deeper slot is rewritten before it is read
            pathLen.put(depth + 1, pathLen.get(depth) + name.length() + 1);
        }
    }
    return res;
}

# python
# LC 388 - Longest Absolute File Path
# IDEA: HASH MAP by DEPTH — path_len[d] = prefix length for children at depth d; overwrite, never pop
# time = O(n), space = O(depth)
class Solution(object):
    def lengthLongestPath(self, input):
        res = 0
        path_len = {0: 0}   # depth-0 entries have an empty prefix

        for line in input.split('\n'):
            name = line.lstrip('\t')
            depth = len(line) - len(name)

            if '.' in name:
                res = max(res, path_len[depth] + len(name))
            else:
                # NOTE !!! overwrite the slot for depth+1 — any stale deeper slot is rewritten before it is read
                path_len[depth + 1] = path_len[depth] + len(name) + 1

        return res

// java
// LC 636 - Exclusive Time of Functions
// IDEA: SCOPE STACK of function ids — the RUNNING function is always the stack top
// time = O(n), space = O(n)
public int[] exclusiveTime(int n, List<String> logs) {

    int[] res = new int[n];
    Deque<Integer> stack = new ArrayDeque<>(); // ids of functions currently RUNNING
    int prev = 0;  // timestamp where the current "run slice" started

    for (String log : logs) {
        String[] p = log.split(":");       // {id, "start"|"end", timestamp}
        int id = Integer.parseInt(p[0]);
        int t = Integer.parseInt(p[2]);

        if (p[1].equals("start")) {
            /**
             *  NOTE !!!
             *   the caller (stack top) ran during [prev, t) -> credit it,
             *   then it gets PREEMPTED by the new callee
             */
            if (!stack.isEmpty()) {
                res[stack.peek()] += t - prev;
            }
            stack.push(id);
            prev = t;
        } else {
            /**
             *  NOTE !!!
             *   "end at t" is INCLUSIVE -> the slice is [prev, t], hence `+ 1`
             *   and the caller resumes at t + 1
             */
            res[stack.pop()] += t - prev + 1;
            prev = t + 1;
        }
    }

    return res;
}

# python
# LC 636 - Exclusive Time of Functions
# IDEA: SCOPE STACK of function ids — the RUNNING function is always the stack top
# time = O(n), space = O(n)
class Solution(object):
    def exclusiveTime(self, n, logs):
        res = [0] * n
        stack = []    # ids of functions currently RUNNING (top = executing now)
        prev = 0      # start of the current time slice

        for log in logs:
            fid, typ, t = log.split(':')
            fid, t = int(fid), int(t)

            if typ == 'start':
                # the caller ran on [prev, t) before being preempted
                if stack:
                    res[stack[-1]] += t - prev
                stack.append(fid)
                prev = t
            else:
                # 'end' timestamp is INCLUSIVE -> [prev, t] => + 1
                res[stack.pop()] += t - prev + 1
                prev = t + 1

        return res

n = 2, logs = ["0:start:0","0:start:2","0:end:5","1:start:6","1:end:6","0:end:7"]

log          credit (to stack top)        stack      prev   res
0:start:0    (stack empty)                [0]        0      [0, 0]
0:start:2    res[0] += 2 - 0     = 2      [0, 0]     2      [2, 0]   <- recursive call, same id
0:end:5      res[0] += 5 - 2 + 1 = 4      [0]        6      [6, 0]
1:start:6    res[0] += 6 - 6     = 0      [0, 1]     6      [6, 0]   <- zero-length slice, harmless
1:end:6      res[1] += 6 - 6 + 1 = 1      [0]        7      [6, 1]
0:end:7      res[0] += 7 - 7 + 1 = 1      []         8      [7, 1]   -> answer [7, 1]

# python
# LC 636 - Exclusive Time of Functions
# IDEA: normalise every log to a half-open BOUNDARY (end:t -> t + 1), so one formula credits both
# time = O(n), space = O(n)
class Solution(object):
    def exclusiveTime(self, n, logs):
        res = [0] * n
        stack = []
        prev = 0      # boundary where the current slice began
        for log in logs:
            fid, typ, t = log.split(':')
            fid, t = int(fid), int(t)
            boundary = t if typ == 'start' else t + 1
            if stack:
                # the stack top ran on [prev, boundary)
                res[stack[-1]] += boundary - prev
            if typ == 'start':
                stack.append(fid)
            else:
                stack.pop()
            prev = boundary
        return res