Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-09-26 17:41:33
https://leetcode.com/problems/remove-duplicate-letters/description
316. Remove Duplicate Letters
给你一个只包含小写字母的字串 s,求出移除所有重复字符后的字串是什么,这个字串的
字典顺序需是最小。
思路:
1.先遍历一次字串 s 求出每个字符出现的最后一个位置。
2.再遍历一次 s ,若当前字符尚未被添加过,将该字符加入集合并标记为已经添加,下
次遇到已经添加过的字符时可以跳过(后面才添加当前字符字典序会更大),集合这
边为了满足题目要求字符的相对位置不可变(不可对阵列排序,只能删除特定位置字
元),可以用Stack 去模拟字串操作。
3.当我们加入完元素前,我们可以检查模拟字串的 Stack 的尾端元素,如果当前字符比
Stack 的尾端元素小,我们移除前面的字符可以使字典顺序变更大,但是移除前需要确
定这个字符后面还会出现,我们可以检查第一步算出来的 lastIdx[] 得知,如果满足
条件就一直移除 Stack 中的字符,并把被移除的字符标记为未访问。
4.最后把 Stack 里面的元素倒序转为 String 即是最小的不重复字串。
Java Code:

Links booklink

Contact Us: admin [ a t ] ucptt.com