堆疊（Stack）

# python
# LC 1047 - Remove All Adjacent Duplicates In String
# IDEA: the stack holds the reduced prefix; a char equal to the top cancels it, otherwise it joins
# time = O(n), space = O(n)
def removeDuplicates(s):
    stack = []                       # the reduced prefix, top = last surviving char
    for ch in s:
        if stack and stack[-1] == ch:
            stack.pop()              # ch cancels its neighbour; the char below becomes adjacent
        else:
            stack.append(ch)
    return ''.join(stack)            # bottom -> top is left -> right order

// java
// LC 1047 - Remove All Adjacent Duplicates In String
// IDEA: the stack holds the reduced prefix; a char equal to the top cancels it, otherwise it joins
// time = O(n), space = O(n)
public String removeDuplicates(String s) {
    Deque<Character> stack = new ArrayDeque<>();   // top = last surviving char
    for (char ch : s.toCharArray()) {
        if (!stack.isEmpty() && stack.peek() == ch) {
            stack.pop();                           // cancel, and expose the char below
        } else {
            stack.push(ch);
        }
    }
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        sb.append(stack.pollLast());               // the bottom is the leftmost survivor
    }
    return sb.toString();
}

s = "abbaca"
ch   action          stack
a    push            a
b    push            a b
b    cancels top     a
a    cancels top     (empty)    <- the cancel exposed 'a', which the next 'a' then cancels
c    push            c
a    push            c a        -> "ca"

# 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: needs a non-empty stack AND the matching partner on top
            if c in pairs:
                if not stack or stack.pop() != pairs[c]:
                    return False
            # opener
            else:
                stack.append(c)
        # leftover openers were never closed
        return not stack

// 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)) {
            if (st.isEmpty()) {
                return false;            // a closer with nothing open
            }
            char top = st.pop();         // unbox to char before comparing
            if (top != pairs.get(c)) {
                return false;            // wrong partner
            }
        } else {
            st.push(c);
        }
    }

    return st.isEmpty();                 // leftover openers -> invalid
}

# python
# IDEA: the stack holds indices still waiting for a warmer day; a warmer `val` answers every one it pops
# time = O(n), space = O(n)
# LC 739 - Daily Temperatures (next greater element, as a distance)
def daily_temperatures(temperatures):
    n = len(temperatures)
    res = [0] * n                 # 0 = no warmer day ahead
    stack = []                    # indices, temperatures non-increasing bottom -> top (equal ones stay)
    for i, val in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < val:
            j = stack.pop()
            res[j] = i - j        # i is the first warmer day after j
        stack.append(i)
    return res

// java
// IDEA: the stack holds indices still waiting for a warmer day; a warmer value answers every one it pops
// time = O(n), space = O(n)
// LC 739 - Daily Temperatures (next greater element, as a distance)
public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] res = new int[n];                    // 0 = no warmer day ahead
    Deque<Integer> stack = new ArrayDeque<>(); // indices, temperatures non-increasing (equal ones stay)

    // Traverse the array from left to right
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
            int j = stack.pop();
            res[j] = i - j;                    // i is the first warmer day after j
        }
        stack.push(i);
    }
    return res;
}

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
i  val   pops (j -> res[j])          stack (indices)
0  73    -                           [0]
1  74    0 -> 1                      [1]
2  75    1 -> 1                      [2]
3  71    -                           [2, 3]
4  69    -                           [2, 3, 4]
5  72    4 -> 1, 3 -> 2              [2, 5]
6  76    5 -> 1, 2 -> 4              [6]
7  73    -                           [6, 7]      -> [1, 1, 4, 2, 1, 1, 0, 0]

# python
# LC 155 - Min Stack
# 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]

// java
// LC 155 - Min Stack
// IDEA: 2 STACKS — stack holds the elements, minValues holds each layer's minimum
// time = O(1) per operation, space = O(n)
class MinStack {
    private final Deque<Integer> stack = new ArrayDeque<>();
    private final Deque<Integer> minValues = new ArrayDeque<>();   // one entry per layer

    public void push(int val) {
        stack.push(val);
        if (minValues.isEmpty()) {
            minValues.push(val);
        } else {
            minValues.push(Math.min(val, minValues.peek()));
        }
    }

    public void pop() {
        stack.pop();
        minValues.pop();          // the layer's state leaves with it
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minValues.peek();  // 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

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

# python
# LC 155 - Min Stack, one stack of (value, min_so_far) tuples
# IDEA: each layer carries its own minimum next to its value
# 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]

# python
# LC 155 - Min Stack, auxiliary non-increasing stack
# IDEA: mins holds only the values that were a minimum when pushed; '<=' keeps duplicate minima
# time = O(1) per operation, space = O(n) worst case
class MinStack(object):

    def __init__(self):
        self.stack = []
        self.mins = []                 # non-increasing bottom -> top; top = current minimum

    def push(self, val):
        self.stack.append(val)
        if not self.mins or val <= self.mins[-1]:
            self.mins.append(val)      # '<=': a second copy of the minimum gets its own entry

    def pop(self):
        if self.stack.pop() == self.mins[-1]:
            self.mins.pop()            # the minimum is leaving, so its entry leaves too

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

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

// java
// LC 155 - Min Stack, auxiliary non-increasing stack
// IDEA: mins holds only the values that were a minimum when pushed; '<=' keeps duplicate minima
// time = O(1) per operation, space = O(n) worst case
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();                  // unbox before comparing
        if (v == mins.peek()) {
            mins.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return mins.peek();
    }
}

# 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)
            # 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)
            # mirrored push 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);
        // 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();
        res.addFirst(node.val);   // addFirst == "append, then reverse", done incrementally
        if (node.left != null) {
            st.push(node.left);
        }
        if (node.right != null) {
            st.push(node.right);
        }
    }
    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

            # 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

// 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;

    // stack.get(d) = length of "dir1/dir2/.../" for the current branch at depth d,
    // trailing '/' included -> the 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);

        // 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;
}

"dir\n\tsubdir2\n\t\tfile.ext"
line         depth   stack after            res
"dir"        0       [0, 4]      ("dir/")
"subdir2"    1       [0, 4, 12]  ("dir/subdir2/")
"file.ext"   2       [0, 4, 12]             12 + 8 = 20

# 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:
                # overwrite the slot for depth+1 — a stale deeper slot is rewritten before it is read
                path_len[depth + 1] = path_len[depth] + len(name) + 1

        return res

// 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 {
            // overwrite the slot for depth+1 — a stale deeper slot is rewritten before it is read
            pathLen.put(depth + 1, pathLen.get(depth) + name.length() + 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

// 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")) {
            // the caller (stack top) ran during [prev, t) -> credit it, then it is PREEMPTED
            if (!stack.isEmpty()) {
                res[stack.peek()] += t - prev;
            }
            stack.push(id);
            prev = t;
        } else {
            // "end at t" is INCLUSIVE -> the slice is [prev, t], hence `+ 1`; the caller resumes at 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