当前位置：首页 > news >正文

贪心与单调栈的艺术：从三道 LeetCode 题看最小字典序问题（316/402/1081）

news 来源：原创 2025/5/10 7:05:26

前言

欢迎来到我的算法探索博客，在这里，我将通过解析精选的LeetCode题目，与您分享深刻的解题思路、多元化的解决方案以及宝贵的实战经验，旨在帮助每一位读者提升编程技能，领略算法之美。
👉更多高频有趣LeetCode算法题

在字符串处理的众多问题中，“最小字典序”是一类典型的优化问题，要求我们在一系列操作约束下构造出字典序最小的字符串。LeetCode 316（去除重复字母）、402（移掉 K 位数字）、1081（不同字符的最小子序列）这三道题，尽管表面上考察的内容不同，但都围绕着同一个核心目标：如何在给定条件下，使最终结果的字典序尽可能小。

解决这类问题的关键在于 贪心策略 + 单调栈。贪心策略的核心思想是每一步都选择当前最优解，确保最终答案的整体最优；单调栈则用于维护一个满足字典序要求的递增结构，同时保证结果的合法性，例如去重或限制字符个数。通过合理地运用这两种技巧，我们可以在遍历过程中动态调整答案，确保最终构造出的字符串是全局最优的。

这一策略不仅适用于字符串去重（如 316、1081），还可以用于数字最小化（如 402），甚至在更广泛的子序列优化问题中也有所应用。本文将通过对这三道题的详细解析，帮助你掌握 贪心 + 单调栈 在最小字典序问题中的应用，让你在面对类似问题时能够迅速找到最佳解法。

402. 移掉 K 位数字	316. 去除重复字母
1081. 不同字符的最小子序列	/

实战：经典例题讲解

402. 移掉 K 位数字

🪴题目描述

在这里插入图片描述

🍁核心思路

1. 贪心策略 + 单调栈

核心思想：要让最终的数值最小，高位数字尽可能小是关键。因此，我们需要从左到右遍历字符串，在允许删除 k 次的前提下，尽可能让高位数字更小。
单调栈的作用：使用 StringBuilder 模拟一个单调非递减栈。遍历过程中，如果当前字符比栈顶字符小，且还有删除次数（k > 0），就不断弹出栈顶字符（删除高位较大的数字），直到栈顶字符不大于当前字符。

2. 遍历字符串，动态调整栈

具体步骤：
1. 遍历每个字符时，检查栈顶字符是否比当前字符大：
  - 如果是，则弹出栈顶字符（相当于删除一个高位较大的数字），并减少 k。
  - 重复这一过程，直到栈顶字符不大于当前字符，或者 k 用完。
2. 将当前字符加入栈中。
示例：
输入 num = "1432219", k = 3：
- 遍历到 '4' 时，栈为 ['1']，'1' < '4'，直接加入 → ['1', '4']。
- 遍历到 '3' 时，发现 '4' > '3'，删除 '4'（k=2），栈变为 ['1']，加入 '3' → ['1', '3']。
- 遍历到 '2' 时，发现 '3' > '2'，删除 '3'（k=1），栈变为 ['1']，加入 '2' → ['1', '2']。
- 最终结果为 "12219"，删除剩余 k=1 次末尾字符 → "1219"。

3. 处理剩余的删除次数

如果遍历完字符串后，k 仍未用完（例如原字符串已经是单调递增的），则直接从栈末尾删除剩余的 k 位，因为末尾的数字是最大的，删除它们对数值影响最小。
- 示例：num = "12345", k = 2 → 删除末尾两位 '4', '5'，结果为 "123"。

4. 处理前导零

删除所有前导零（例如 "0200" → "200"）。
如果结果为空或全为零，返回 "0"。

🌏代码实现

Java

class Solution {public String removeKdigits(String num, int k) {StringBuilder sb = new StringBuilder();for (char a : num.toCharArray()) {while (k > 0 && sb.length() > 0 && sb.charAt(sb.length() - 1) > a) {k--;sb.deleteCharAt(sb.length() - 1);}sb.append(a);}// 如果 k 仍然大于 0，需要继续删除最后的 k 个字符while (k > 0 && sb.length() > 0) {sb.deleteCharAt(sb.length() - 1);k--;}// 移除前导零int start = 0;for (int i = 0; i < sb.length(); i++) {if (sb.charAt(i) == '0')start++;elsebreak;}// 如果 sb 为空或全是 0，则返回 "0"String result = sb.substring(start);return result.isEmpty() ? "0" : result;}
}

Python

class Solution:def removeKdigits(self, num, k):result = []for c in num:while k > 0 and result and result[-1] > c:result.pop()k -= 1result.append(c)# 如果 k 仍然大于 0，删除最后的 k 个字符result = result[:-k] if k else result# 移除前导零finalResult = "".join(result).lstrip('0')return finalResult if finalResult else "0"

C++

class Solution {
public:string removeKdigits(string num, int k) {string result;for (char c : num) {while (k > 0 && !result.empty() && result.back() > c) {result.pop_back();k--;}result.push_back(c);}// 如果 k 仍然大于 0，删除最后的 k 个字符while (k > 0 && !result.empty()) {result.pop_back();k--;}// 移除前导零int start = 0;while (start < result.size() && result[start] == '0') {start++;}// 构造最终字符串string finalResult = result.substr(start);return finalResult.empty() ? "0" : finalResult;}
};

316. 去除重复字母

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

🪴题目描述

这俩题基本上一致，换个方法名就行。

在这里插入图片描述

🍁核心思路（针对Java）

1. 统计字符出现次数

首先，我们需要知道每个字符在字符串中出现的次数，以便后续判断是否可以移除某个字符（如果后面还有相同的字符，就可以放心移除当前字符）。
使用一个 Map<Character, Integer> 来记录每个字符的剩余次数。

2. 维护单调递增栈

我们需要一个栈（这里用 StringBuilder 模拟栈）来构建最终的结果。这个栈的特点是 单调递增，也就是说，栈中的字符是按字典序从小到大排列的。
遍历字符串时，对于每一个字符：
- 如果它已经在栈中（通过 isUsed 数组标记），则直接跳过，因为题目要求去重。
- 如果它不在栈中，则需要决定是否将其加入栈中。

3. 贪心策略：弹出栈顶字符

在将当前字符加入栈之前，我们需要检查栈顶的字符是否比当前字符大，并且栈顶字符在后面还会出现（通过 map 判断剩余次数）。
- 如果满足条件，说明栈顶字符可以被移除，因为后面还有机会再次加入它。这样做的目的是让字典序更小。
- 弹出栈顶字符后，需要将其标记为未使用（isUsed 数组更新）。

4. 加入当前字符

当栈顶字符不再比当前字符大，或者栈顶字符后面不会再出现时，将当前字符加入栈中，并标记为已使用。

5. 返回结果

最终，栈中的字符就是去重后字典序最小的结果。

示例

以字符串 "cbacdcbc" 为例：

遍历到 'c'，加入栈中，栈为 ['c']。
遍历到 'b'，发现 'c' 比 'b' 大且后面还有 'c'，弹出 'c'，加入 'b'，栈为 ['b']。
遍历到 'a'，发现 'b' 比 'a' 大且后面还有 'b'，弹出 'b'，加入 'a'，栈为 ['a']。
遍历到 'c'，加入栈中，栈为 ['a', 'c']。
遍历到 'd'，加入栈中，栈为 ['a', 'c', 'd']。
遍历到 'c'，'c' 已经在栈中，跳过。
遍历到 'b'，加入栈中，栈为 ['a', 'c', 'd', 'b']。
遍历到 'c'，'c' 已经在栈中，跳过。

最终结果为 "acdb"。

通过这种 贪心 + 单调栈 的方法，我们能够高效地解决问题，同时保证结果的字典序最小。

🌏代码实现

Java

class Solution {public String removeDuplicateLetters(String S) {// 统计每个字母的出现次数char[] s = S.toCharArray();Map<Character, Integer> map = new HashMap<>();for (char a : s) {map.put(a, map.getOrDefault(a, 0) + 1);}StringBuilder sb = new StringBuilder();boolean[] isUsed = new boolean[26];for (char sss : s) {map.put(sss, map.get(sss) - 1);  // 直接获取值，无需 getOrDefaultif (isUsed[sss - 'a']) continue; // 如果已经在结果中，则跳过// 维护一个单调递增栈while (sb.length() > 0 && sb.charAt(sb.length() - 1) > sss && map.get(sb.charAt(sb.length() - 1)) > 0) {isUsed[sb.charAt(sb.length() - 1) - 'a'] = false; // 标记移除的字符为未使用sb.deleteCharAt(sb.length() - 1);}sb.append(sss);isUsed[sss - 'a'] = true; // 标记该字符已经被使用}return sb.toString();}
}

Python

class Solution(object):def removeDuplicateLetters(self, s):count = Counter(s)is_used = set()result = []for c in s:count[c] -= 1if c in is_used:continuewhile result and result[-1] > c and count[result[-1]] > 0:is_used.remove(result.pop())result.append(c)is_used.add(c)return ''.join(result)

C++

class Solution {
public:string removeDuplicateLetters(string s) {unordered_map<char, int> count;vector<bool> isUsed(26, false);for (char c : s) {count[c]++;}string result;for (char c : s) {count[c]--;if (isUsed[c - 'a']) continue;while (!result.empty() && result.back() > c && count[result.back()] > 0) {isUsed[result.back() - 'a'] = false;result.pop_back();}result.push_back(c);isUsed[c - 'a'] = true;}return result;}
};

结语

这三道题看似不同，但本质上都是在解决一个问题：如何构造字典序最小的字符串。它们的核心思路都是 贪心 + 单调栈，通过维护一个递增的结构，在每一步选择当前最优的字符，同时确保后续字符仍然满足条件。

316 和 1081 的重点是去重，确保每个字符只出现一次，同时让字典序最小。
402 则是通过删除数字来让数值最小，虽然不需要去重，但同样需要保证每一步的选择是最优的。

无论是去掉重复字符、删掉多余数字，还是优化子序列，这套方法都能帮我们高效地找到最优解。掌握了 贪心 + 单调栈 的思路，这类问题就能迎刃而解了！

如果您渴望探索更多精心挑选的高频LeetCode面试题，以及它们背后的巧妙解法，欢迎您访问我的博客，那里有我精心准备的一系列文章，旨在帮助技术爱好者们提升算法能力与编程技巧。

👉更多高频有趣LeetCode算法题

在我的博客中，每一篇文章都是我对算法世界的一次深入挖掘，不仅包含详尽的题目解析，还有我个人的心得体会、优化思路及实战经验分享。无论是准备面试还是追求技术成长，我相信这些内容都能为您提供宝贵的参考与启发。期待您的光临，让我们共同在技术之路上不断前行！

前言

实战：经典例题讲解

🪴题目描述

🍁核心思路

1. 贪心策略 + 单调栈

2. 遍历字符串，动态调整栈

3. 处理剩余的删除次数

4. 处理前导零

🌏代码实现

Java

Python

C++

🪴题目描述

🍁核心思路（针对Java）

1. 统计字符出现次数

2. 维护单调递增栈

3. 贪心策略：弹出栈顶字符

4. 加入当前字符

5. 返回结果

示例

🌏代码实现

Java

Python

C++

结语

相关文章：