LeetCode 1081. 不同字符的最小子序列

约 5 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 华为 滴滴
标签
字符串 栈 贪心 单调栈

题目描述

✅ 1081. 不同字符的最小子序列

image-20260928225617744

题意分析

从小写字母字符串中选出字典序最小的子序列，要求原串中每种出现过的字符都恰好保留一次。可以删除字符，但保留字符的相对顺序不能改变，因此不能直接把不同字母排序。

解法：单调栈维护候选

核心思路

[!blue]

字典序由第一个不同的位置决定，所以应尽量让较小的字符排在前面。用栈保存当前选出的子序列，用 used[c] 表示字符 c 是否已在栈中，预先计算 last[c] 表示它最后一次出现的位置。

扫描到下标 i 的字符 c 时，若它已经在栈中，就跳过这次出现；保留较早的同一字符能给后面的选择留下更多位置。若尚未选择它，就检查栈顶 top：只有 top > c 且 last[top] > i，才能弹出栈顶。前一个条件说明让 c 提前会使字典序更小，后一个条件保证 top 以后还能补回，不会缺少某种字符。

弹掉这样的栈顶后，未改变的前缀相同，第一个变化的位置由较大的 top 换成了较小的 c，结果一定更优。因此连续弹出所有满足条件的栈顶，再加入 c。每次弹出都要清除对应的 used 标记，允许该字符在之后重新入选。

如果栈顶没有后续副本，它必须留在当前字符前；如果栈顶更小，保留它在前更优。这两种情况都应停止弹栈，所以候选栈不一定始终递增。扫描结束后，每种字符都已保留一次，栈底到栈顶就是满足原顺序的最小字典序答案。

解题步骤

  1. 扫描一次字符串，记录各字符的最后出现位置 last。
  2. 再次从左到右扫描。当前字符已被 used 标记时直接跳过。
  3. 栈非空、栈顶比当前字符大且以后还会出现时，弹出栈顶，并将其 used 设为 false。
  4. 将当前字符入栈，并将其 used 设为 true。
  5. 扫描完成后按栈中现有顺序返回字符串，无需反转。

代码实现

class Solution {
    public String smallestSubsequence(String s) {
        int[] last = new int[26];

        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }

        boolean[] used = new boolean[26];
        StringBuilder stack = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int idx = c - 'a';

            // 当前已保留的字符不再重复加入。
            if (used[idx]) {
                continue;
            }

            while (stack.length() > 0) {
                char top = stack.charAt(stack.length() - 1);

                // 只有替换更优且以后能补回，才撤销栈顶。
                if (top > c && last[top - 'a'] > i) {
                    // 撤销后允许这个字符在后续位置重新入选。
                    used[top - 'a'] = false;
                    stack.deleteCharAt(stack.length() - 1);
                } else {
                    break;
                }
            }

            stack.append(c);
            used[idx] = true;
        }

        return stack.toString();
    }
}

func smallestSubsequence(s string) string {
    last := make([]int, 26)
    for i := 0; i < len(s); i++ {
        last[s[i]-'a'] = i
    }

    used := make([]bool, 26)
    stack := make([]byte, 0)

    for i := 0; i < len(s); i++ {
        c := s[i]
        idx := c - 'a'
        // 当前已保留的字符不再重复加入。
        if used[idx] {
            continue
        }

        for len(stack) > 0 {
            top := stack[len(stack)-1]
            // 只有替换更优且以后能补回，才撤销栈顶。
            if top > c && last[top-'a'] > i {
                // 撤销后允许这个字符在后续位置重新入选。
                used[top-'a'] = false
                stack = stack[:len(stack)-1]
            } else {
                break
            }
        }

        stack = append(stack, c)
        used[idx] = true
    }

    return string(stack)
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 n 为字符串长度；每次字符出现至多入栈、出栈各一次，两次扫描总体为线性。
  • 空间复杂度：$O(1)$，字母表固定为 26 个小写字母，两个辅助数组和栈都只需常数空间。

关键点总结

[!green]

  • 弹栈要同时满足字典序收益与后续仍可补回。
  • 栈底到顶就是答案顺序，不需要反转。

易错点总结

[!yellow]

  • 只看大小就弹，会丢掉某种字符的最后机会。
  • 弹栈不恢复 used，会阻止该字符再次加入。
  • 直接把不同字符排序，可能得到不是原串子序列的结果。
  • used 表示当前是否在栈中，不是这个字符是否曾经出现或入栈过。

相似题目

题目 难度 关联与区别
402. 移掉 K 位数字 中等 同样贪心弹出不利栈顶，本题要求每种字符恰好一次，弹出前要确保后面可补回。
321. 拼接最大数 困难 同样选择最优子序列，原题限制最终长度，本题限制字符种类覆盖及不重复。
316. 去除重复字母 中等 保持单调候选并在后续仍可补足时弹出较差元素；本题选择每种不同字符一次的最小字典序子序列，该题每种字符保留一次并追踪剩余次数。
1673. 找出最具竞争力的子序列 中等 保持单调候选并在后续仍可补足时弹出较差元素；本题选择每种不同字符一次的最小字典序子序列，该题保留固定长度的最具竞争力子序列。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/58180207
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！