单调栈 · 字典序与贪心

1. 核心原理

本章讨论的问题模板是：

给定一个序列（字符串或数组）和一组约束（删 k 个字符 / 每个字符恰好出现一次 / 拼成长度 k 的子序列），求满足约束的字典序最小（或最大）子序列。

母题是 LeetCode 402 移掉 K 位数字。这类问题与上一章 next-greater 共享单调栈骨架，但单调性的"意义"完全不同——前两章是"栈顶等到了答案"，本章是"栈顶被嫌弃了"。

暴力解的瓶颈

枚举所有保留 n - k 个字符的组合 C(n, n-k)，逐一比较字典序。n ≤ 10⁵ 时组合数为指数级，不可行；即便 n = 20，C(20, 10) = 184756，加上每个候选还要 O(n) 构造，整体 O(n × C(n, k)) 仍远超时限。

贪心 + 单调栈维护字典序前缀

引入一个栈，栈中存储"已经确定要放进结果"的字符（按相对顺序）。不变量：扫描到位置 i 时，栈中字符序列就是 s[0..i] 上在当前剩余删配额约束下能达到的字典序最小前缀。

从左到右扫描 s。对当前字符 c：

1. 若栈非空、栈顶 stack[-1] > c、且仍有删除配额，则弹出栈顶（消耗 1 个删配额）。靠左的高位对字典序影响更大，用一个更小的字符替换栈顶位的较大字符，整体严格更小。
2. 重复第 1 步，直到栈空、栈顶 ≤ c 或删配额用尽。
3. 将 c 入栈。

扫描结束后，若仍有剩余删配额（输入本身单调不降时会发生），从栈尾继续删足够多个字符。

贪心正确性

考虑某一步遇到栈顶 a 与当前字符 c < a、且仍有删配额。若最优解保留 a 而删去 c，构造一个新解：删 a 而保留 c。两解删除字符数相同，前若干位完全一致，第一处不同位上新解为 c、原解为 a，由 c < a 知新解字典序更小，与原解最优矛盾。故"栈顶大于当前 → 弹出栈顶"是局部最优且导致全局最优。

复杂度

每个字符至多入栈一次、出栈一次，时间 O(n)，空间 O(n)。带"必选字符"或"双数组拼接"等约束时常数因子上升，但量级不变。

带约束变种的差异只在 pop / push 处的守门条件上：

• LC 316 / 1081（每字符恰好一次）：pop 之前要确认"栈顶字符在 s 剩余部分仍会出现"；push 之前要确认"当前字符尚未在栈中"。
• LC 1673 / 最具竞争力：删配额 = n - k，扫完按 k 截断。
• LC 2030（含 letter 至少 repetition 次）：pop 前要确认"删了之后仍能凑齐 letter 配额"。
• LC 321（双数组拼接）：枚举两数组各取多少个，子问题转化为单数组上的"取 t 个使字典序最大"，再做字典序合并。

与 next-greater 章节的 pop 语义对比

本章代码骨架与 next-greater 几乎一致，但 pop 的含义截然不同：

前者的 pop 是"被服务"，后者的 pop 是"被替换"——共用骨架，语义不同。

2. 通用模板

下面给出"删除 k 个字符使剩下的字典序最小"的通用骨架。求字典序最大时把 stack[-1] > c 翻成 stack[-1] < c。

def lex_smallest_after_removal(s: str, k_remove: int) -> str:
    """
    从 s 中删除 k_remove 个字符（保持其他字符相对顺序），
    返回字典序最小的剩余字符串。
    """
    stack = []                                  # 存字符；从底到顶不严格递增
    k = k_remove
    for c in s:
        # 栈顶比 c 大且仍有删配额：弹出栈顶（局部最优）
        while stack and stack[-1] > c and k > 0:
            stack.pop()
            k -= 1
        stack.append(c)
    # 扫完 k 还没用光（输入本身单调不降）：从尾部继续删
    while k > 0:
        stack.pop()
        k -= 1
    return ''.join(stack)

String lexSmallestAfterRemoval(String s, int kRemove) {
    StringBuilder stack = new StringBuilder();   // 用 StringBuilder 当栈
    int k = kRemove;
    for (char c : s.toCharArray()) {
        // 栈顶比 c 大且仍有删配额：弹出栈顶（局部最优）
        while (stack.length() > 0
                && stack.charAt(stack.length() - 1) > c
                && k > 0) {
            stack.deleteCharAt(stack.length() - 1);
            k--;
        }
        stack.append(c);
    }
    // 扫完 k 还没用光（输入本身单调不降）：从尾部继续删
    while (k > 0) {
        stack.deleteCharAt(stack.length() - 1);
        k--;
    }
    return stack.toString();
}

string lexSmallestAfterRemoval(const string& s, int kRemove) {
    string st;                                   // 直接用 string 当栈
    st.reserve(s.size());
    int k = kRemove;
    for (char c : s) {
        // 栈顶比 c 大且仍有删配额：弹出栈顶（局部最优）
        while (!st.empty() && st.back() > c && k > 0) {
            st.pop_back();
            k--;
        }
        st.push_back(c);
    }
    // 扫完 k 还没用光（输入本身单调不降）：从尾部继续删
    while (k > 0) {
        st.pop_back();
        k--;
    }
    return st;
}

模板上有四处需要明确：

• pop 条件 > 严格而非 >=：相等时不弹，保留靠左的位置不会改变字典序，却节省了一次删配额，留给后面可能更有价值的位置使用。
• 删配额来源：LC 402 给定 k；LC 1673 隐含 k = n - target_length；LC 316 / 321 隐含 k = n - distinct_count 或来自双数组划分。模板里 k 是统一接口。
• 尾部清理：当输入本身满足"单调不降"（如 "12345"），主循环里 pop 条件永远不触发，删配额未用尽。必须在扫描结束后从栈尾再删 k 个，否则在这类输入上会得到错误答案。
• 栈的容器选型：Python 用 list、C++ 用 string、Java 用 StringBuilder 比 Deque<Character> 更省常数，且最终拼字符串时不需反向。

3. 母题精讲

LeetCode 402 移掉 K 位数字

链接：LeetCode 402

题意：给一个非负整数字符串 num 和一个整数 k。从 num 中删除 k 位数字（保持其他数字的相对顺序），使剩下的数字字符串表示的整数最小。返回该最小数字的字符串形式（删除前导零）。

数据范围：

• num.length：1 到 10⁵
• k：0 到 num.length
• num：只含 '0'–'9' 的字符，且不以 0 开头（除非 num 本身就是 "0"）

示例：

输入：num = "1432219", k = 3
输出："1219"
解释：删除 3 个数字 4, 3, 2，剩下 "1219" 最小。

输入：num = "10200", k = 1
输出："200"
解释：删除首位 1，剩下 "0200"，去前导零得 "200"。

输入：num = "10", k = 2
输出："0"
解释：全删，按约定返回 "0"。

暴力解：枚举所有 C(n, k) 种删法

最朴素的想法是枚举所有删 k 位的方式，挨个比较：

from itertools import combinations

class Solution:
    def removeKdigits_brute(self, num: str, k: int) -> str:
        n = len(num)
        keep = n - k                           # 保留几位
        if keep == 0:
            return "0"
        best = None
        # 枚举所有保留的下标组合
        for idx in combinations(range(n), keep):
            s = ''.join(num[i] for i in idx).lstrip('0') or "0"
            if best is None or s < best or (len(s) < len(best)):
                best = s
        return best

C(n, k) 在 n = 10⁵ 时是天文数字，秒级 TLE。即使 n = 20，C(20, 10) 就是 18 万了。

关键观察：贪心局部最优 = 全局最优

换个思路。我们从左到右扫 num，对每个新数字 c：

• 如果栈顶比 c 大，说明"把栈顶留着、删掉 c"不如"删掉栈顶、留着 c"——因为靠左的高位影响更大，删掉一个大的高位换成小的高位，整体一定更小。
• 所以 pop 掉栈顶（消耗一次删除配额），继续看下一个栈顶，直到栈顶 ≤ c 或者删除配额用完。
• 然后把 c push 进栈。

扫完后如果 k 还没用完（数字是单调递增的，比如 "12345", k=2），从栈尾再删 k 位。最后处理前导零。

这就是单调（不严格）递增栈——每次保证栈底到栈顶不下降。下面这个交互演示走一遍 num = "1432219", k = 3 的过程：

最终结果 "1219"。整个过程每个字符至多 push 一次、pop 一次，O(n)。

贪心正确性证明

为什么"栈顶 > 当前 → pop 栈顶"是局部最优？反证。假设最优解 X 在某一步没有 pop 栈顶 a（栈顶位置 i，当前是 c < a，位置 j > i）。那么 X 在结果里位置 i 是 a，位置 j 是 c（或不是 c）。

构造另一个解 X'：把 X 里的 a 换成 c（即删 i 位置的 a，保留 j 位置的 c），删字符总数不变。比较 X 和 X'：

• 前 i-1 位完全相同
• 第 i 位：X 是 a，X' 是 c < a → X' 更小

所以 X' < X，与 X 是最优矛盾。所以贪心局部最优蕴含全局最优，单调栈策略正确。

这道题用单调栈不是因为"找下一个更大"那种结构，而是用来维护一个目前能给出的最小字典序前缀——这是单调栈在字典序问题里的核心用途。下面进入例题。

4. 例题（三道）

按"额外约束递增"排：纯删 → 必选每字符 → 双数组拼接。每道带 follow-up 续到下一题。

4.1 LC 402 移掉 K 位数字

回到本章开头那道题。在模板基础上加两步收尾：处理前导零、处理全删的边界。

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        for c in num:
            while stack and stack[-1] > c and k > 0:
                stack.pop()
                k -= 1
            stack.append(c)
        # k 还没用光：从尾部继续删（数字单调递增的情形）
        while k > 0:
            stack.pop()
            k -= 1
        # 去前导零
        result = ''.join(stack).lstrip('0')
        return result if result else "0"

class Solution {
    public String removeKdigits(String num, int k) {
        StringBuilder stack = new StringBuilder();   // 用 StringBuilder 当栈
        for (char c : num.toCharArray()) {
            while (stack.length() > 0 && stack.charAt(stack.length() - 1) > c && k > 0) {
                stack.deleteCharAt(stack.length() - 1);
                k--;
            }
            stack.append(c);
        }
        while (k > 0) {
            stack.deleteCharAt(stack.length() - 1);
            k--;
        }
        // 去前导零
        int i = 0;
        while (i < stack.length() && stack.charAt(i) == '0') i++;
        String result = stack.substring(i);
        return result.isEmpty() ? "0" : result;
    }
}

class Solution {
public:
    string removeKdigits(string num, int k) {
        string st;                                      // 直接用 string 当栈
        st.reserve(num.size());
        for (char c : num) {
            while (!st.empty() && st.back() > c && k > 0) {
                st.pop_back();
                k--;
            }
            st.push_back(c);
        }
        // k 还没用光：从尾部继续删（数字单调递增的情形）
        while (k > 0) {
            st.pop_back();
            k--;
        }
        // 去前导零
        int i = 0;
        while (i < (int)st.size() && st[i] == '0') i++;
        string result = st.substr(i);
        return result.empty() ? "0" : result;
    }
};

复杂度 O(n) 时间、O(n) 空间。

注意两个收尾细节：

第一，扫完 k 还没用光的情形。比如 num = "12345", k = 2：数字本身单调递增，pop 条件 stack[-1] > c 一次都不触发，栈最后是 "12345"。这时候要从尾部多删 2 位，得 "123"。

第二，前导零处理。num = "10200", k = 1 时栈跑完是 "0200"，要 lstrip('0') 得 "200"；如果剩空字符串，按题意返回 "0"。

Follow-up：上面是"删 k 个使最小"，没有"必选"约束。如果题目要求每个出现过的字符在结果里恰好出现一次呢？

4.2 LC 316 去除重复字母

链接：LeetCode 316

题意：给一个由小写字母组成的字符串 s，请去除其中所有重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

数据范围：

• s.length：1 到 10⁴
• s 只含小写字母

示例：

输入：s = "bcabc"
输出："abc"

输入：s = "cbacdcbc"
输出："acdb"

这道题在 LC 402 模板上加两条约束：

• pop 栈顶 c 之前，要确认"c 在后面还会出现"——否则丢了 c 之后再也没机会放回来，违反"每字符至少出现一次"
• push 当前字符 c 之前，要确认"c 还没在栈里"——否则栈里会出现两次

实现上需要：

• count：每个字符在剩余未扫部分中的剩余次数
• in_stack：每个字符是否已经在栈里

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        from collections import Counter
        count = Counter(s)                          # 每字符剩余出现次数
        in_stack = set()
        stack = []
        for c in s:
            count[c] -= 1                           # 当前位置之后，c 剩这么多
            if c in in_stack:
                continue                            # 已在栈里，不重复 push
            # 栈顶比 c 大，且栈顶在后面还会出现，可以 pop
            while stack and stack[-1] > c and count[stack[-1]] > 0:
                in_stack.discard(stack.pop())
            stack.append(c)
            in_stack.add(c)
        return ''.join(stack)

复杂度 O(n)（每字符至多 push/pop 一次，in_stack 检查 O(1)，count 是预处理 O(n)）。空间 O(σ)，σ 是字符集大小（这里 26）。

正确性证明：跟 LC 402 类似，但多了"必选"约束。pop 栈顶时必须确认后面还有它——这保证了最终结果包含所有出现过的字符。如果栈顶在后面不再出现，那它现在必须留着，宁可结果不那么小也得保证完整性。

Follow-up：上面两题都是在一个字符串上做。如果题目给两个数组，让你各从中挑出一段，按相对顺序合并出长度为 k 的最大数呢？

4.3 LC 321 拼接最大数

链接：LeetCode 321

题意：给两个长度分别为 m 和 n 的整数数组 nums1 和 nums2（元素 0–9）。从中各挑出一些数字，保持它们在原数组里的相对顺序，拼成一个长度为 k 的数组。返回字典序最大的拼接结果。要求 k ≤ m + n。

数据范围：

• m, n：1 到 500
• nums1[i]、nums2[i]：0 到 9
• k：1 到 m + n

示例：

输入：nums1 = [3, 4, 6, 5], nums2 = [9, 1, 2, 5, 8, 3], k = 5
输出：[9, 8, 6, 5, 3]

这道题是 LC 402 的进阶——三步组合：

1. 挑：对每个 i 满足 max(0, k - n) ≤ i ≤ min(m, k)，从 nums1 挑 i 个组成字典序最大的子序列、从 nums2 挑 k - i 个组成字典序最大的子序列。每次"挑 t 个使字典序最大"用单调栈模板（保留 t 个 = 删 len - t 个，pop 条件改成 stack[-1] < c）。
2. 合：把 nums1 的子序列和 nums2 的子序列按"字典序合并"成长度 k 的数组——每次取两个数组当前位置开头的字典序更大的那个。注意是字典序，不是单纯比较首元素。
3. 比：所有 i 的拼接结果里取字典序最大。

class Solution:
    def maxNumber(self, nums1: list[int], nums2: list[int], k: int) -> list[int]:
        m, n = len(nums1), len(nums2)

        def pick_max(nums: list[int], t: int) -> list[int]:
            """从 nums 中按相对顺序挑 t 个，组成字典序最大的子序列"""
            drop = len(nums) - t
            stack = []
            for x in nums:
                while stack and stack[-1] < x and drop > 0:
                    stack.pop()
                    drop -= 1
                stack.append(x)
            return stack[:t]

        def merge(a: list[int], b: list[int]) -> list[int]:
            """字典序合并 a 和 b 成长度 |a| + |b| 的最大数组"""
            result = []
            while a or b:
                if a > b:                           # Python 列表比较就是字典序
                    result.append(a.pop(0))
                else:
                    result.append(b.pop(0))
            return result

        best = []
        for i in range(max(0, k - n), min(m, k) + 1):
            cand = merge(pick_max(nums1, i), pick_max(nums2, k - i))
            if cand > best:
                best = cand
        return best

复杂度：pick_max 是 O(m + n)，merge 是 O(k × (m + n))（Python 列表比较是字典序，本身可能扫一段），外层枚举 i 是 O(k)，总 O(k² × (m + n))。m, n ≤ 500, k ≤ 1000 下 5 × 10⁸ 量级，临界。如果 TLE，把 merge 改用游标 + 切片比较实现，避免 pop(0) 的 O(n) 开销，见 §5。

工程版的 merge 用 tuple(a[ai:]) > tuple(b[bi:]) 比 a > b 然后 pop(0) 高效（避免 pop(0) 的 O(n) 开销）。LC 上 Python 接受率有点低，C++ / Java 用专门字典序比较函数。

注意 merge 里的字典序比较：当两个数组当前首位相等时，不能简单取任意一个——要看后续。比如 a = [6, 7]，b = [6, 0, 4]，第一位都是 6，但 a > b 因为 7 > 0。Python 的列表比较 a > b 自动处理这种情况；其他语言要手写。

5. 边界、易错与复杂度

pop 条件用 > 还是 >=

字典序最小求最优时通常用 >（严格大于）：相等时不 pop，保留靠左的位置不影响字典序（因为相等）。

LC 402 是这样。LC 316 / 1673 也是。

少数题用 >=（比如要"尽量贴近某个目标"），具体看题。

"k 还没用光"的尾部清理

如果输入序列本身已经满足单调性（递增 → 求最小、递减 → 求最大），pop 条件永远不触发，k 一次也没用。这时候要从栈尾把剩余 k 位删掉。

LC 402 的 while k > 0: stack.pop() 就是处理这个。忘了这一步会在单调递增/递减输入上 WA。

前导零 / 空串处理

数字字符串题（LC 402、LC 2030）要小心：

• 删完前导零的字符串可能是空的，要返回 "0"
• 不要在中间用 int(s) 转整数——num 长度可达 10⁵，超出任意整数类型范围

"必选"约束的实现细节

LC 316 这种题，count[c] 必须在循环开始先减 1，再判断 pop 条件——因为 pop 条件问的是"c 之后还会不会出现"，"之后"不包含当前位置。如果先判断再减，会多算一次。

in_stack 用 set 而不是数组也行，但数组（[False] * 26）更快，因为 set 哈希开销。

LC 321 的工程优化

merge 用 pop(0) 是 O(n)——总复杂度退化。工程上用游标 (ai, bi) 加切片比较 tuple(a[ai:]) > tuple(b[bi:])：

def merge(a, b):
    result = []
    ai, bi = 0, 0
    while ai < len(a) or bi < len(b):
        if a[ai:] > b[bi:]:                     # 切片比较 = 字典序
            result.append(a[ai]); ai += 1
        else:
            result.append(b[bi]); bi += 1
    return result

虽然切片 a[ai:] 在 Python 是 O(len) 拷贝，但每次 result 加一个元素，总开销可控。如果 TLE，把 merge 改用游标 + 切片比较实现，避免 pop(0) 的 O(n) 开销，见 §5。

复杂度速查

7. 小结

单调栈的第三类用法——维护当前能给出的字典序前缀。这一族题的核心是贪心局部最优蕴含全局最优：靠左的位影响更大，所以"删一个大的高位换一个小的高位"几乎总是值得，除非额外约束（必选字符 / 长度 / 配额）不允许。

记三个关键工具：

• 通用模板：单调（不严格）递增/递减栈 + 删配额计数 + 扫完尾部清理。
• 字典序"必选"约束：用 count 数组追踪后续剩余次数，pop 前确认"删了仍能凑齐"。
• 双数组拼接：枚举切分点 + 各自单调栈 + 字典序合并。

单调栈系列三章打通：基础下一个更大 / 矩形面积贡献法 / 本章字典序。下一个大主题按 CLAUDE.md 大纲是 网格图（DFS / BFS / 综合应用）。

对应灵神题单：单调栈字典序 / 贪心字典序

进一步阅读：灵茶山艾府《单调栈题单》第三部分；LeetCode 字符串栈标签 下高频题