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

【算法】单调栈题单——字典序最小⭐（一种类型的模板题）

news 2025/8/25 19:40:40

文章目录

题目列表
- 316. 去除重复字母⭐⭐⭐⭐⭐（类型题模板：单调栈，字典序最小）
- 221021天池-03. 整理书架（保留数量为 limit 的字典序最小）
- 402. 移掉 K 位数字（最多删除 k 次 + 前导零的处理）
- 321. 拼接最大数🚹🚹🚹🚹🚹（繁琐）（分成两组+合并）💩
相关链接

题目列表

从第一题模板题入手。

316. 去除重复字母⭐⭐⭐⭐⭐（类型题模板：单调栈，字典序最小）

https://leetcode.cn/problems/remove-duplicate-letters/description/

在这里插入图片描述
注意：该题与 316 https://leetcode.cn/problems/remove-duplicate-letters/ 相同

冷静分析，先去掉一个字符，该去掉哪一个？为了字典序越小，肯定要越往前的字符越小越好，那么就应该将最靠前的，且满足s[i]>s[i+1]的那个s[i]删掉即可。

怎么模拟多次这个过程呢？由于最先被删掉的一定更靠前，所以可以使用单调栈从前到后维护保留下来的字符。

除此之外，

要求每种原来就有的字符至少会保留下来一次，因此如果之后没有这种字符了，那么就不应该将其pop出栈。
如果一个字符已经在栈中了，那么后续的字符就不需要再加入栈了。

可以直接使用StringBuilder作为栈。

class Solution {public String removeDuplicateLetters(String s) {int[] cnt = new int[128];for (char ch: s.toCharArray()) cnt[ch]++;   // 记录各个字符剩余的数量StringBuilder ans = new StringBuilder();    // StringBuilder可以当栈使用for (char ch: s.toCharArray()) {cnt[ch]--;                              // 将剩余数量-1if (ans.indexOf(String.valueOf(ch)) != -1) continue;         // 如果前面已经有ch了，后面不需要再有了// 将stk中比当前ch更大且后面还有剩余的字符pop出去while (ans.length() > 0 && ch <= ans.charAt(ans.length() - 1) && cnt[ans.charAt(ans.length() - 1)] > 0) {ans.deleteCharAt(ans.length() - 1);}ans.append(ch);}return ans.toString();}
}

也可以使用栈，再转换成字符串。

class Solution {public String removeDuplicateLetters(String s) {int[] cnt = new int[128];for (char ch: s.toCharArray()) cnt[ch]++;   // 记录各个字符剩余的数量Deque<Character> stk = new ArrayDeque<>();for (char ch: s.toCharArray()) {cnt[ch]--;                              // 将剩余数量-1if (stk.contains(ch)) continue;         // 如果前面已经有ch了，后面不需要再有了// 将stk中比当前ch更大且后面还有剩余的字符pop出去while (!stk.isEmpty() && ch <= stk.peek() && cnt[stk.peek()] > 0) {stk.pop();}stk.push(ch);}// 将栈中的结果转成String返回StringBuilder ans = new StringBuilder();while (!stk.isEmpty()) ans.append(stk.pop());return ans.reverse().toString();}
}

221021天池-03. 整理书架（保留数量为 limit 的字典序最小）

https://leetcode.cn/contest/tianchi2022/problems/ev2bru/

在这里插入图片描述
提示：

1 <= order.length <= 10^5
1 <= limit <= 10
1 <= order[i] <= 10^6

class Solution {public int[] arrangeBookshelf(int[] order, int limit) {Deque<Integer> stk = new ArrayDeque<>();// 分别记录剩余的数量，在栈中的数量Map<Integer, Integer> cnt_residue = new HashMap<>(), cnt2 = new HashMap<>();for (int x: order) cnt_residue.merge(x, 1, Integer::sum);for (int x: order) {cnt_residue.merge(x, -1, Integer::sum);if (cnt2.getOrDefault(x, 0) >= limit) continue;     // 如果栈中已经有足够的x了，就不再添加进去// 要求栈中的元素+剩余的元素>limit才会被弹出while (!stk.isEmpty() && x < stk.peek() && cnt_residue.get(stk.peek()) + cnt2.getOrDefault(stk.peek(), 0) > limit) {cnt2.merge(stk.peek(), -1, Integer::sum);stk.pop();}stk.push(x);cnt2.merge(x, 1, Integer::sum);}int n = stk.size();int[] ans = new int[n];for (int i = n - 1; i >= 0; --i) {ans[i] = stk.pop();}return ans;}
}

402. 移掉 K 位数字（最多删除 k 次 + 前导零的处理）

https://leetcode.cn/problems/remove-k-digits/description/

在这里插入图片描述

跟之前题目的区别在于，最多删除k次。
以及0可以不删，留着当前导零直接去除。

class Solution {public String removeKdigits(String num, int k) {Deque<Character> stk = new ArrayDeque<>();for (char x: num.toCharArray()) {while (!stk.isEmpty() && x < stk.peek() && k > 0) {stk.pop();k--;}stk.push(x);}// 如果还有没用的k，从后往前删除while (!stk.isEmpty() && k-- > 0) stk.pop();if (stk.size() == 0) return "0";    StringBuilder ans = new StringBuilder();while (!stk.isEmpty()) ans.append(stk.pop());// 去除前导零while (ans.length() > 1 && ans.charAt(ans.length() - 1) == '0') ans.deleteCharAt(ans.length() - 1);return ans.reverse().toString();}
}

321. 拼接最大数🚹🚹🚹🚹🚹（繁琐）（分成两组+合并）💩

https://leetcode.cn/problems/create-maximum-number/description/