跳至主要內容

 

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

Info

数据结构精品课open in new window递归算法专题课open in new window 限时附赠网站会员,全新纸质书《labuladong 的算法笔记》open in new window 出版,签名版限时半价!

读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:

LeetCode力扣难度
1081. Smallest Subsequence of Distinct Charactersopen in new window1081. 不同字符的最小子序列open in new window🟠
316. Remove Duplicate Lettersopen in new window316. 去除重复字母open in new window🟠

关于去重算法,应该没什么难度,往哈希集合里面塞不就行了么?

最多给你加点限制,问你怎么给有序数组原地去重,这个我们前文 双指针技巧秒杀七道数组题目 讲过。

本文讲的问题应该是去重相关算法中难度最大的了,把这个问题搞懂,就再也不用怕数组去重问题了。

这是力扣第 316 题「去除重复字母open in new window」,题目如下:

这道题和第 1081 题「不同字符的最小子序列」的解法是完全相同的,你可以把这道题的解法代码直接粘过去把 1081 题也干掉。

题目的要求总结出来有三点:

要求一、要去重

要求二、去重字符串中的字符顺序不能打乱 s 中字符出现的相对顺序

要求三、在所有符合上一条要求的去重字符串中,字典序最小的作为最终结果。

上述三条要求中,要求三可能有点难理解,举个例子。

比如说输入字符串 s = "babc",去重且符合相对位置的字符串有两个,分别是 "bac""abc",但是我们的算法得返回 "abc",因为它的字典序更小。

按理说,如果我们想要有序的结果,那就得对原字符串排序对吧,但是排序后就不能保证符合 s 中字符出现顺序了,这似乎是矛盾的。

其实这里会借鉴后文 单调栈解题框架 中讲到的「单调栈」的思路,没看过也无妨,等会你就明白了。

本文剩余内容为会员内容,请先购买 网站会员 open in new window ,然后 借助 Chrome 插件解锁网页 open in new window 或者 点这里open in new window 跳转小鹅通查看。

共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释