约 646 字大约 2 分钟数据结构栈设计

Info
数据结构精品课 和 递归算法专题课 限时附赠网站会员,全新纸质书《labuladong 的算法笔记》 出版,签名版限时半价!
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
1081. Smallest Subsequence of Distinct Characters | 1081. 不同字符的最小子序列 | 🟠 |
316. Remove Duplicate Letters | 316. 去除重复字母 | 🟠 |
关于去重算法,应该没什么难度,往哈希集合里面塞不就行了么?
最多给你加点限制,问你怎么给有序数组原地去重,这个我们前文 双指针技巧秒杀七道数组题目 讲过。
本文讲的问题应该是去重相关算法中难度最大的了,把这个问题搞懂,就再也不用怕数组去重问题了。
这是力扣第 316 题「去除重复字母」,题目如下:

这道题和第 1081 题「不同字符的最小子序列」的解法是完全相同的,你可以把这道题的解法代码直接粘过去把 1081 题也干掉。
题目的要求总结出来有三点:
要求一、要去重。
要求二、去重字符串中的字符顺序不能打乱 s
中字符出现的相对顺序。
要求三、在所有符合上一条要求的去重字符串中,字典序最小的作为最终结果。
上述三条要求中,要求三可能有点难理解,举个例子。
比如说输入字符串 s = "babc"
,去重且符合相对位置的字符串有两个,分别是 "bac"
和 "abc"
,但是我们的算法得返回 "abc"
,因为它的字典序更小。
按理说,如果我们想要有序的结果,那就得对原字符串排序对吧,但是排序后就不能保证符合 s
中字符出现顺序了,这似乎是矛盾的。
其实这里会借鉴后文 单调栈解题框架 中讲到的「单调栈」的思路,没看过也无妨,等会你就明白了。
共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释