題目

https://leetcode.com/problems/remove-duplicate-letters

題解

關于什么是“字典序”

字典序，換成數字更好理解一點 a:1,b:2,c:3 那么：acdb => 1342 dcab => 4312
4312 > 1342 所以 dcab > acdb 也可以想象在英語詞典里，acdb會比dcab出現得更早，所以acdb的字典序更小

思路

看了評論區，知道這題是個單調棧，但是不知道怎么構造單調棧，然后。。看了答案。

參考：官方視頻題解

class Solution {public String removeDuplicateLetters(String s) {char[] chars = s.toCharArray();int[] lastIndex = new int[26]; // 每個字母最后一次出現的位置for (int i = 0; i < chars.length; i++) {lastIndex[chars[i] - 'a'] = i;}Deque<Character> stack = new ArrayDeque<>(); // 單調棧boolean[] inStack = new boolean[26];for (int i = 0; i < chars.length; i++) {if (inStack[chars[i] - 'a']) continue; // 新字母以及出現在棧中，則跳過while (!stack.isEmpty() && stack.peekLast() >= chars[i] && i < lastIndex[stack.peekLast() - 'a']) {// 當前字母造成序列非增，且后面還會出現前一個字母，則丟棄前一個字母char c = stack.pollLast();inStack[c - 'a'] = false;}stack.offerLast(chars[i]);inStack[chars[i] - 'a'] = true;}StringBuilder sb = new StringBuilder();for (Character item : stack) {sb.append(item);}return sb.toString();} }

總結

以上是生活随笔為你收集整理的leetcode 316. Remove Duplicate Letters | 316. 去除重复字母（单调栈解法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。