贪心字符串：重构字符串与翻转

本篇覆盖三道经典的「单调栈 + 贪心」字符串/数字题目，它们的核心思路高度相似：在遍历过程中，利用栈维护当前最优序列，当发现栈顶元素"不如"当前元素时弹出栈顶。

一、去除重复字母（LeetCode 316）

题目描述

给你一个字符串 s，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证：

1. 每个字母只保留一个
2. 返回结果的字典序最小

示例：s = "bcabc" → "abc"，s = "cbacdcbc" → "acdb"

解题思路

暴力思路：枚举所有去重后的排列，挑字典序最小的——显然时间爆炸。

贪心洞察：遍历字符串，对每个字符 c：

• 如果 c 已经在栈中，跳过
• 否则看栈顶字符 top：如果 top > c（字典序更大）且 top 在后面还会出现（后续还有机会放入），那就弹出 top，让 c 取代它的位置
• 这样就能在"不丢失任何字母"的前提下，让栈底到栈顶尽可能字典序小

需要三个辅助结构：

1. count[26]：每个字母剩余出现次数（判断后面还有没有机会）
2. inStack[26]：标记字母是否已在栈中（避免重复加入）
3. 栈：维护当前最优结果

示例 s = "cbacdcbc" 的模拟过程：

字符  栈状态          说明
 c    [c]           push c
 b    [b]           b < c，弹 c（c 后面还有），push b
 a    [a]           a < b，弹 b（b 后面还有），push a
 c    [a,c]         push c
 d    [a,c,d]       push d
 c    [a,c,d]       c 已在栈中，跳过
 b    [a,b]         b < d，弹 d（d 后面没有了❌ → 不弹）
                    等等，d 后面没有了所以不弹 d
                    ← 实际：b < c 且 c 后面还有吗？c 还剩 0 个 → 也不弹
                    → 最终 push b：[a,c,d,b]
 c    [a,c,d,b]     c 已在栈中，跳过

结果："acdb"

代码实现

public String removeDuplicateLetters(String s) {
    int[] count = new int[26];       // 每个字母剩余出现次数
    boolean[] inStack = new boolean[26]; // 字母是否已在栈中
    for (char c : s.toCharArray()) count[c - 'a']++;

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

    for (char c : s.toCharArray()) {
        count[c - 'a']--;            // 剩余可用次数 -1

        if (inStack[c - 'a']) continue; // 已在栈中，跳过

        // 栈顶 > c 且栈顶字母后面还会出现 → 弹出栈顶
        while (!stack.isEmpty() && stack.peek() > c
               && count[stack.peek() - 'a'] > 0) {
            inStack[stack.pop() - 'a'] = false;
        }

        stack.push(c);
        inStack[c - 'a'] = true;
    }

    StringBuilder sb = new StringBuilder();
    for (char c : stack) sb.append(c);
    return sb.reverse().toString();
}

复杂度

• 时间：O(n)，每个字符最多入栈出栈各一次
• 空间：O(1)，栈最多 26 个字母

二、移掉 K 位数字（LeetCode 402）

题目描述

给定一个以字符串表示的非负整数 num 和一个整数 k，移除这个数中的 k 位数字，使得剩下的数字最小。返回字符串形式的结果（不含前导零）。

示例：num = "1432219", k = 3 → "1219"

解题思路

关键问题：移掉哪 k 位才能让剩余数最小？

贪心洞察：从高位（左侧）开始，如果某一位数字比它后面的数字大，移除它会让整体变小。这是因为高位的影响力远大于低位。

用单调递增栈实现：

• 遍历每一位数字 d
• 若栈顶 > d 且还有删除配额（k > 0），弹出栈顶（相当于删除它），k--
• 将 d 入栈
• 遍历完后，若 k 仍 > 0，从末尾继续删除

num = "1432219", k = 3  模拟：

步骤  字符  栈         k   操作
1     '1'  [1]        3   push
2     '4'  [1,4]      3   push（4 > 1，不弹）
3     '3'  [1,3]      2   3 < 4，弹 4，k=2，push 3
4     '2'  [1,2]      1   2 < 3，弹 3，k=1，push 2
5     '2'  [1,2,2]    1   push（2 ≥ 2，不弹）
6     '1'  [1,1]      0   1 < 2，弹 2，k=0，push 1
                           再弹？k=0 了，停止
      实际：1 < 2，弹栈顶 2，k=0；再看 2>1 但 k=0 了
      → [1,2,1] ... 让我重新精确模拟：

精确模拟：
'1' → [1]                     k=3
'4' → [1,4]                   k=3 (4>1 不弹)
'3' → 3<4, 弹4, k=2 → [1,3]  k=2, push → [1,3]
'2' → 2<3, 弹3, k=1 → [1,2]  k=1, push → [1,2]
'2' → 2=2 不弹, push → [1,2,2]  k=1
'1' → 1<2, 弹2, k=0 → [1,2,1]  k=0, push → [1,2,1]  
       k=0 停止
'9' → push → [1,2,1,9]        k=0

结果："1219" ✓

代码实现

public String removeKdigits(String num, int k) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char d : num.toCharArray()) {
        // 栈顶比当前大且还有删除配额 → 弹出栈顶
        while (k > 0 && !stack.isEmpty() && stack.peek() > d) {
            stack.pop();
            k--;
        }
        stack.push(d);
    }

    // 如果 k 还没用完，从末尾删除（此时栈已单调递增）
    while (k-- > 0) stack.pop();

    // 从栈底到栈顶构建结果
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) sb.append(stack.pollLast());

    // 去除前导零
    while (sb.length() > 1 && sb.charAt(0) == '0') sb.deleteCharAt(0);

    return sb.length() == 0 ? "0" : sb.toString();
}

复杂度

• 时间：O(n)，每个字符最多入栈出栈各一次
• 空间：O(n)

三、拼接最大数（LeetCode 321）

题目描述

给定两个长度分别为 m 和 n 的整数数组 nums1 和 nums2，从中选出 k 个数字（保持各自数组内的相对顺序），拼接后组成一个长度为 k 的最大数。

示例：nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5 → [9,8,6,5,3]

解题思路

这道题比前两道复杂，需要分解为三个子问题：

1. 枚举分配：从 nums1 取 k1 个，从 nums2 取 k2 = k - k1 个，k1 的范围从 max(0, k-n) 到 min(k, m)
2. 单调栈选最大子序列：在单个数组中选出 size 个元素组成字典序最大的子序列——和"移掉 K 位数字"思路相反，这里维护单调递减栈
3. 归并两个子序列：将两个最大子序列合并成一个最大数

nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5

枚举 k1=0: 从 nums2 取 5 个最大 → [9,5,8,3] ← 不够
       k1=1: nums1 取 1 个最大=[6], nums2 取 4=[9,5,8,3] → 合并
       k1=2: nums1 取 2=[6,5], nums2 取 3=[9,8,3] → 合并
       ...

对每种分配，选最大候选者即可

代码实现

public int[] maxNumber(int[] nums1, int[] nums2, int k) {
    int m = nums1.length, n = nums2.length;
    int[] best = new int[k];

    // 枚举从 nums1 取 k1 个
    for (int k1 = Math.max(0, k - n); k1 <= Math.min(k, m); k1++) {
        int[] sub1 = maxSubsequence(nums1, k1);
        int[] sub2 = maxSubsequence(nums2, k - k1);
        int[] candidate = merge(sub1, sub2);
        if (compare(candidate, 0, best, 0) > 0) {
            best = candidate;
        }
    }
    return best;
}

// 用单调栈从 nums 中选出 size 个元素，使字典序最大
private int[] maxSubsequence(int[] nums, int size) {
    int n = nums.length, drop = n - size; // 可丢弃 drop 个
    int[] stack = new int[size];
    int top = 0;
    for (int num : nums) {
        // 栈顶更小且还能丢弃 → 弹出
        while (drop > 0 && top > 0 && stack[top - 1] < num) {
            top--;
            drop--;
        }
        if (top < size) stack[top++] = num;
        else drop--; // 栈满了，当前元素也丢弃
    }
    return stack;
}

// 合并两个子序列为一个最大数
private int[] merge(int[] a, int[] b) {
    int[] res = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    while (i < a.length || j < b.length) {
        // 字典序比较决定先取哪个
        res[k++] = compare(a, i, b, j) >= 0 ? a[i++] : b[j++];
    }
    return res;
}

// 从位置 i 和 j 开始的字典序比较
private int compare(int[] a, int i, int[] b, int j) {
    while (i < a.length && j < b.length) {
        if (a[i] != b[j]) return a[i] - b[j];
        i++; j++;
    }
    return (a.length - i) - (b.length - j);
}

复杂度

• 时间：O(k × (m + n + k))，枚举 k 种分配，每种需要 O(m+n) 选子序列 + O(k) 合并
• 空间：O(k)

总结

这三道题的共同本质是单调栈贪心：

万能模板：遍历序列，用栈维护候选结果；当栈顶"不满意"且还有"替换机会"时弹出栈顶。