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