Leetcode316去除重复字母

Leetcode 316: 去除重复字母 是一道考察贪心思想与栈在字符串操作中使用的经典题目。该题的目标是让结果字符串既是 字典序最小，又不包含重复字符，而且在原字符串中字符的相对顺序要保持不变。下面列举几种解法，并分析其实现方式和时间复杂度。

---

题目描述

输入：给定一个字符串 s，其中包含小写字母。 输出：返回 s 的一个子序列，该子序列需要满足以下条件：

包含原字符串的所有字符（去重后），每个字符只出现一次。所有字符的相对顺序与原字符串中一致。输出字典序最小的结果。

---

示例输入输出：

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

---

解法 1：贪心 + 单调栈 思路 从后往前构造结果: 使用一个栈模拟最终结果字符串。按顺序遍历字符串，将字符加入栈中时确保： 每个字符只出现一次；字典序尽可能小。 计算当前字符是否可以移除： 一个字符可以从栈中移除，如果移除它不会导致后续字符串无法构成完整的唯一字符集合。使用 lastIndex[] 数组记录每个字符最后出现的索引位置，判断是否还有后续机会添加该字符。 辅助判断当前字符是否已在结果中： 用一个 inStack 记录栈中是否已有某个字符，避免重复。 实现步骤 遍历过程: 如果当前字符已在栈中，跳过。如果当前字符比栈顶字符字典序小，并且栈顶字符在后面还会出现，则弹出栈顶字符，使得当前字符能够被加入栈中。 最终栈中存储了构造好的结果。

---

代码模板 class Solution { public String removeDuplicateLetters(String s) { int[] lastIndex = new int[26]; // 记录字符最后出现的位置 boolean[] inStack = new boolean[26]; // 标记字符是否在栈中 // 记录每个字符最后出现的位置 for (int i = 0; i < s.length(); i++) { lastIndex[s.charAt(i) - 'a'] = i; } Deque<Character> stack = new ArrayDeque<>(); // 用双端队列模拟单调栈 for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); // 如果当前字符已经在栈中，跳过 if (inStack[c - 'a']) { continue; } // 当栈顶元素的字典序大于当前字符，并且栈顶元素在后面还会出现，可以弹出栈顶元素 while (!stack.isEmpty() && stack.peekLast() > c && lastIndex[stack.peekLast() - 'a'] > i) { char removed = stack.pollLast(); inStack[removed - 'a'] = false; // 标记移除 } // 将当前字符加入栈中 stack.offerLast(c); inStack[c - 'a'] = true; // 标记加入 } // 将栈中字符拼接成结果字符串 StringBuilder result = new StringBuilder(); for (char c : stack) { result.append(c); } return result.toString(); } }

---

复杂度分析 时间复杂度： 遍历字符串一次 O(n)；栈的入栈与出栈操作总时间复杂度为 O(n)；因此，总体复杂度为 O(n)。 空间复杂度： 栈、数组 lastIndex 和 inStack，额外空间为 O(26)，即 O(1)（因为最多只有 26 个小写字母）。

---

适用场景 题目明确要求字典序最小，并且需要在保证原字符顺序基础上去重时，这种方法最优。

---

解法 2：贪心递归法 思路 贪心核心： 整个问题的目标是找到字典序最小的合法子序列，可以利用递归分治思想逐步找到当前字典序最小的字符。每次递归，选择剩余字符串中字典序最小的字符作为当前分割点，然后递归处理剩余部分。 递归具体实现： 首先遍历字符串，找到在当前范围内未重复字符的最小字符。将其作为结果的第一个字符，并递归寻找剩余部分的结果。

---

代码模板 class Solution { public String removeDuplicateLetters(String s) { if (s.isEmpty()) { return ""; } // 统计每个字符出现的次数 int[] count = new int[26]; for (char c : s.toCharArray()) { count[c - 'a']++; } // 找到字典序最小的字符作为当前结果的第一个字符 char minChar = 'z' + 1; int minIndex = -1; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c < minChar) { minChar = c; minIndex = i; } count[c - 'a']--; if (count[c - 'a'] == 0) { break; // 找到第一个未重复的字符，停止。 } } // 递归处理剩余部分，去掉 minChar 后面的所有 minChar String remaining = s.substring(minIndex + 1).replaceAll(String.valueOf(minChar), ""); return minChar + removeDuplicateLetters(remaining); } }

---

复杂度分析 时间复杂度： 每次递归遍历一次字符串，最坏情况下需要递归 26 次。总时间复杂度为 O(26 * n) = O(n)（近似线性）。 空间复杂度： 由于递归调用堆栈，空间复杂度为 O(26) = O(1)。

---

适用场景 对于数据规模小的输入（如只包含少量字符，或字符串长度较小），递归法更易于理解。如果题目允许更高复杂度约束，这种形式可用于竞赛或面试时快速实现。

---

解法 3：基于贪心的双索引法 思路

这是单调栈法的另一种实现形式：

从左到右维护当前最优字符选择： 预先统计每个字符在剩余部分的最远位置。遍历时构造结果，始终从当前子串范围内优先选择字典序最小且未重复的字符。 动态规划全局最优解。

---

快速 AC 策略 优先选择单调栈法（解法 1）: 时间复杂度 O(n)，实现简单，能快速通过。注意使用 boolean[] 和 int[] 做标记，减少重复计算。 在面试中优先写递归法（解法 2）: 简单易实现，能快速写出功能完备的代码，但对长字符串性能可能不如栈法。

无论比赛还是面试，熟练掌握单调栈模板均可快速 AC！