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：
----------------------------------------------------
class Solution {
public String removeDuplicateLetters(String s) {
int[] lastIdx = new int[26];
for (int i = 0; i < s.length(); i++) {
lastIdx[s.charAt(i) - 'a'] = i;
}
Stack<Integer> stack = new Stack<>();
boolean[] visited = new boolean[26];
for (int i = 0; i < s.length(); i++) {
int chIdx = s.charAt(i) - 'a';
if (visited[chIdx]) continue;
while (!stack.isEmpty() && stack.peek() > chIdx && i <
lastIdx[stack.peek()]) {
visited[stack.pop()] = false;
}
stack.push(chIdx);
visited[chIdx] = true;
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append((char) (stack.pop() + 'a'));
}
return sb.reverse().toString();
}
}
----------------------------------------------------
--
https://i.imgur.com/YPBHGGE.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1695721296.A.CE9.html