Stack — 實戰題解

# python
# LC 1209 - Remove All Adjacent Duplicates in String II
# IDEA: stack of [char, run length]; a run that reaches k is popped whole
# time = O(n), space = O(n)
class Solution(object):
    def removeDuplicates(self, s, k):
        stack = []                       # [char, run length] — the reduced prefix, run-length encoded
        for ch in s:
            if stack and stack[-1][0] == ch:
                stack[-1][1] += 1
                if stack[-1][1] == k:
                    stack.pop()          # the run reached k: it vanishes, exposing the run below
            else:
                stack.append([ch, 1])
        return ''.join(ch * cnt for ch, cnt in stack)

// java
// LC 1209 - Remove All Adjacent Duplicates in String II
// IDEA: stack of {char, run length}; a run that reaches k is popped whole
// time = O(n), space = O(n)
public String removeDuplicates(String s, int k) {
    Deque<int[]> stack = new ArrayDeque<>();      // {char, run length}, top = last run
    for (char ch : s.toCharArray()) {
        if (!stack.isEmpty() && stack.peek()[0] == ch) {
            stack.peek()[1]++;
            if (stack.peek()[1] == k) {
                stack.pop();                      // the run vanishes, exposing the run below
            }
        } else {
            stack.push(new int[]{ch, 1});
        }
    }
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        int[] run = stack.pollLast();             // the bottom is the leftmost run
        for (int i = 0; i < run[1]; i++) {
            sb.append((char) run[0]);
        }
    }
    return sb.toString();
}

s = "deeedbbcccbdaa", k = 3
ch   stack (runs)                     note
d    [d1]
e    [d1 e1]
e    [d1 e2]
e    [d1]                             e reaches 3 -> popped
d    [d2]                             the pop exposed d, so this d extends it
b    [d2 b1]
b    [d2 b2]
c    [d2 b2 c1]
c    [d2 b2 c2]
c    [d2 b2]                          c reaches 3 -> popped
b    [d2]                             b reaches 3 -> popped (cascade)
d    []                               d reaches 3 -> popped (cascade)
a    [a1]
a    [a2]                             -> "aa"

# python
# LC 735 - Asteroid Collision
# IDEA: stack of survivors; a left-mover fights right-moving tops until one side is gone
# time = O(n), space = O(n)
class Solution(object):
    def asteroidCollision(self, asteroids):
        stack = []                       # survivors, left to right
        for a in asteroids:
            alive = True
            # a collision needs the newcomer moving left and the top moving right
            while alive and a < 0 and stack and stack[-1] > 0:
                if stack[-1] < -a:
                    stack.pop()          # the top explodes; `a` keeps flying left
                    continue
                if stack[-1] == -a:
                    stack.pop()          # equal size: both explode
                alive = False            # `a` explodes (or already did with the top)
            if alive:
                stack.append(a)
        return stack

// java
// LC 735 - Asteroid Collision
// IDEA: stack of survivors; a left-mover fights right-moving tops until one side is gone
// 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();                  // the top explodes, `a` keeps flying
                continue;
            }
            if (stack.peek() == -a) {
                stack.pop();                  // both explode
            }
            alive = false;                    // `a` explodes
        }
        if (alive) {
            stack.push(a);
        }
    }
    int[] res = new int[stack.size()];
    for (int i = res.length - 1; i >= 0; i--) {
        res[i] = stack.pop();                 // pop fills from the right end
    }
    return res;
}

# python
# LC 1249 - Minimum Remove to Make Valid Parentheses
# IDEA: 2 SCANS with a balance counter — drop unmatched ')' left->right, unmatched '(' right->left
# time = O(n), space = O(n) for the two output buffers; O(1) beyond them
class Solution(object):
    def minRemoveToMakeValid(self, s):
        # pass 1: left -> right; a ')' with no '(' open before it can never be matched
        kept = []
        open_cnt = 0
        for c in s:
            if c == ')':
                if open_cnt == 0:
                    continue        # unmatched ')' -> drop
                open_cnt -= 1
            elif c == '(':
                open_cnt += 1
            kept.append(c)

        # pass 2: right -> left, the mirror; a '(' with no ')' open after it can never be matched
        res = []
        close_cnt = 0
        for c in reversed(kept):
            if c == '(':
                if close_cnt == 0:
                    continue        # unmatched '(' -> drop
                close_cnt -= 1
            elif c == ')':
                close_cnt += 1
            res.append(c)

        res.reverse()               # pass 2 built it backwards
        return ''.join(res)

// java
// LC 1249 - Minimum Remove to Make Valid Parentheses
// IDEA: 2 SCANS with a balance counter — drop unmatched ')' left->right, unmatched '(' right->left
// time = O(n), space = O(n) for the two output buffers; O(1) beyond them
public String minRemoveToMakeValid(String s) {
    StringBuilder kept = new StringBuilder();
    int openCnt = 0;
    for (char c : s.toCharArray()) {
        if (c == ')') {
            if (openCnt == 0) {
                continue;      // unmatched ')' -> drop
            }
            openCnt--;
        } else if (c == '(') {
            openCnt++;
        }
        kept.append(c);
    }
    StringBuilder res = new StringBuilder();
    int closeCnt = 0;
    for (int i = kept.length() - 1; i >= 0; i--) {
        char c = kept.charAt(i);
        if (c == '(') {
            if (closeCnt == 0) {
                continue;      // unmatched '(' -> drop
            }
            closeCnt--;
        } else if (c == ')') {
            closeCnt++;
        }
        res.append(c);
    }
    return res.reverse().toString(); // pass 2 built it backwards
}

s = ")((a)"

pass 1, left -> right   )  open=0 -> drop       (  open=1   (  open=2   a   )  open=1
                        kept = "((a)"
pass 2, right -> left   )  close=1   a   (  close=0   (  close=0 -> drop
                        res  = "(a)"

# python
# LC 856 - Score of Parentheses
# IDEA: STACK OF PARTIAL SCORES — one frame per depth, fold child into parent
# time = O(n), space = O(n)
class Solution(object):
    def scoreOfParentheses(self, s):
        stack = [0]                  # stack[-1] = score collected so far at the current depth
        for c in s:
            if c == '(':
                stack.append(0)      # open a frame for the new depth
            else:
                inner = stack.pop()  # close it: "()" scores 1, "(X)" scores 2 * X
                stack[-1] += max(2 * inner, 1)
        return stack[0]

// java
// LC 856 - Score of Parentheses
// IDEA: STACK OF PARTIAL SCORES — one frame per depth, fold child into parent
// time = O(n), space = O(n)
public int scoreOfParentheses(String s) {
    Deque<Integer> st = new ArrayDeque<>();
    st.push(0); // score of the outermost frame
    for (char c : s.toCharArray()) {
        if (c == '(') {
            st.push(0); // open a new (empty) frame
        } else {
            int inner = st.pop();
            st.push(st.pop() + Math.max(2 * inner, 1)); // "()" scores 1, "(X)" scores 2 * X
        }
    }
    return st.pop();
}

# python
# LC 1963 - Minimum Number of Swaps to Make the String Balanced
# IDEA: cancel matched pairs; the residue is "]"*m + "["*m and one swap fixes two pairs
# time = O(n), space = O(n)
class Solution(object):
    def minSwaps(self, s):
        stack = []
        for c in s:
            if c == ']' and stack and stack[-1] == '[':
                stack.pop()              # a matched pair cancels
            else:
                stack.append(c)          # an unmatched ']' or a '[' still open
        # what is left is "]" * m + "[" * m: every ']' sits before every '['
        m = len(stack) // 2
        return (m + 1) // 2              # one swap repairs two of the m pairs

# python
# LC 32 - Longest Valid Parentheses
# IDEA: STACK OF INDICES + `-1` base sentinel; length = i - stack[-1]
# time = O(n), space = O(n)
class Solution(object):
    def longestValidParentheses(self, s):
        stack = [-1]         # bottom = index just before the current valid run (the base)
        best = 0
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            else:
                stack.pop()                       # match the top '(' — or pop the base
                if not stack:
                    stack.append(i)               # unmatched ')' -> it becomes the new base
                else:
                    best = max(best, i - stack[-1])
        return best

// java
// LC 32 - Longest Valid Parentheses
// IDEA: STACK OF INDICES + `-1` base sentinel; length = i - stack.peek()
// time = O(n), space = O(n)
public int longestValidParentheses(String s) {
    Deque<Integer> st = new ArrayDeque<>();
    st.push(-1);                    // base: the index just before the current valid run
    int best = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            st.push(i);
        } else {
            st.pop();               // match the top '(' — or pop the base
            if (st.isEmpty()) {
                st.push(i);         // unmatched ')' -> the new base
            } else {
                best = Math.max(best, i - st.peek());
            }
        }
    }
    return best;
}

s = ")()())"

i  c   action                       stack        best
-  -   init base                    [-1]         0
0  )   pop -1 -> empty -> new base  [0]          0
1  (   push                         [0, 1]       0
2  )   pop 1, i - top = 2 - 0 = 2   [0]          2
3  (   push                         [0, 3]       2
4  )   pop 3, i - top = 4 - 0 = 4   [0]          4  <- answer
5  )   pop 0 -> empty -> new base   [5]          4

# python
# LC 32 - Longest Valid Parentheses
# IDEA: 1D DP — dp[i] = longest valid substring ENDING at i
# time = O(n), space = O(n)
class Solution(object):
    def longestValidParentheses(self, s):
        n = len(s)
        dp = [0] * n                      # dp[i] = longest valid run ENDING at i
        best = 0
        for i in range(1, n):
            if s[i] == '(':
                continue                  # a valid run never ends with '('
            if s[i - 1] == '(':
                # case 1: "...()" -> the new pair + the run ending at i-2
                dp[i] = 2 + (dp[i - 2] if i >= 2 else 0)
            else:
                # case 2: "...))" -> jump over the run ending at i-1 to s[i]'s partner
                open_idx = i - dp[i - 1] - 1
                if open_idx >= 0 and s[open_idx] == '(':
                    dp[i] = dp[i - 1] + 2
                    if open_idx >= 1:
                        dp[i] += dp[open_idx - 1]   # glue on the run that ends before the partner
            best = max(best, dp[i])
        return best

s = "()(())"

i  c   case                                             dp
0  (   '(' ends nothing                                 [0,0,0,0,0,0]
1  )   "()": 2 + dp[-1 -> 0]                            [0,2,0,0,0,0]
2  (   -                                                [0,2,0,0,0,0]
3  (   -                                                [0,2,0,0,0,0]
4  )   "()": 2 + dp[2] = 2                              [0,2,0,0,2,0]
5  )   "))": open_idx = 5 - dp[4] - 1 = 2, s[2] = '('
           dp[5] = dp[4] + 2 + dp[1] = 2 + 2 + 2 = 6    [0,2,0,0,2,6]  <- answer

# python
# LC 32 - Longest Valid Parentheses
# IDEA: 2 SCANS with open/close counters — left->right, then right->left
# time = O(n), space = O(1)
class Solution(object):
    def longestValidParentheses(self, s):
        best = 0
        # pass 1: left -> right; a surplus ')' can never be matched -> reset
        opens = closes = 0
        for c in s:
            if c == '(':
                opens += 1
            else:
                closes += 1
            if opens == closes:
                best = max(best, 2 * closes)
            elif closes > opens:
                opens = closes = 0
        # pass 2: right -> left; catches "(()", where opens stays ahead in pass 1
        opens = closes = 0
        for c in reversed(s):
            if c == '(':
                opens += 1
            else:
                closes += 1
            if opens == closes:
                best = max(best, 2 * opens)
            elif opens > closes:
                opens = closes = 0
        return best

# python
# LC 445 - Add Two Numbers II
# IDEA: TWO STACKS give least-significant-first access without mutating the input
# time = O(n + m), space = O(n + m)
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        s1, s2 = [], []
        while l1:                         # push every digit: popping now yields least significant first
            s1.append(l1.val)
            l1 = l1.next
        while l2:
            s2.append(l2.val)
            l2 = l2.next

        carry = 0
        head = None                       # the answer is built from its tail forwards
        while s1 or s2 or carry:          # a pending carry adds one more digit
            total = carry
            if s1:
                total += s1.pop()
            if s2:
                total += s2.pop()
            carry = total // 10
            node = ListNode(total % 10)
            node.next = head              # prepend: the second reversal puts the digits back in order
            head = node
        return head

// java
// LC 445 - Add Two Numbers II
// IDEA: TWO STACKS give least-significant-first access without mutating the input
// time = O(n + m), space = O(n + m)
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    Deque<Integer> s1 = new ArrayDeque<>();
    Deque<Integer> s2 = new ArrayDeque<>();
    for (ListNode p = l1; p != null; p = p.next) {
        s1.push(p.val);
    }
    for (ListNode p = l2; p != null; p = p.next) {
        s2.push(p.val);
    }
    int carry = 0;
    ListNode head = null;                     // built from the tail forwards
    while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
        int sum = carry;
        if (!s1.isEmpty()) {
            sum += s1.pop();
        }
        if (!s2.isEmpty()) {
            sum += s2.pop();
        }
        carry = sum / 10;
        ListNode node = new ListNode(sum % 10);
        node.next = head;                     // prepend: the second reversal restores the order
        head = node;
    }
    return head;
}