14
一道数组去重的算法题把我整不会了
source link: https://labuladong.github.io/algo/%E9%AB%98%E9%A2%91%E9%9D%A2%E8%AF%95%E7%B3%BB%E5%88%97/%E5%8D%95%E8%B0%83%E6%A0%88%E5%8E%BB%E9%87%8D.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
一道数组去重的算法题把东哥整不会了
👆让天下没有难刷的算法！若 GitBook 访问太慢，可尝试 GiteePages 或 GitHubPages！
相关推荐：
读完本文，你不仅学会了算法套路，还可以顺便去 LeetCode 上拿下如下题目：
关于去重算法，应该没什么难度，往哈希集合里面塞不就行了么？
最多给你加点限制，问你怎么给有序数组原地去重，这个我们旧文 如何高效地给有序数组/链表去重。
本文讲的问题应该是去重相关算法中难度最大的了，把这个问题搞懂，就再也不用怕数组去重问题了。
这是力扣第 316 题「去除重复字母」，题目如下：
这道题和第 1081 题「不同字符的最小子序列」的解法是完全相同的，你可以把这道题的解法代码直接粘过去把 1081 题也干掉。
题目的要求总结出来有三点：
要求一、要去重。
要求二、去重字符串中的字符顺序不能打乱 s 中字符出现的相对顺序。
要求三、在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果。
上述三条要求中，要求三可能有点难理解，举个例子。
比如说输入字符串 s = "babc"，去重且符合相对位置的字符串有两个，分别是 "bac" 和 "abc"，但是我们的算法得返回 "abc"，因为它的字典序更小。
按理说，如果我们想要有序的结果，那就得对原字符串排序对吧，但是排序后就不能保证符合 s 中字符出现顺序了，这似乎是矛盾的。
其实这里会借鉴前文 单调栈解题框架 中讲到的「单调栈」的思路，没看过也无妨，等会你就明白了。
＿＿＿＿＿＿＿＿＿＿＿＿＿
本文只能在 labuladong 公众号查看，关注后可直接搜索本站内容：
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK