leetcode 316. Remove Duplicate Letters | 316. 去除重复字母（单调栈解法）

r囧r小猫 2022-10-19 08:20 79阅读 0赞

## 题目 ##

[https://leetcode.com/problems/remove-duplicate-letters][https_leetcode.com_problems_remove-duplicate-letters]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

##### 关于什么是“字典序” #####

字典序，换成数字更好理解一点 a:1,b:2,c:3 那么：acdb => 1342 dcab => 4312  
4312 > 1342 所以 dcab > acdb 也可以想象在英语词典里，acdb会比dcab出现得更早，所以acdb的字典序更小

##### 思路 #####

看了评论区，知道这题是个单调栈，但是不知道怎么构造单调栈，然后。。看了答案。

参考：[官方视频题解][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

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();
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_remove-duplicate-letters]: https://leetcode.com/problems/remove-duplicate-letters/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/63c0ea969d824bd4a6f42b28b2607835.png
[Link 1]: https://leetcode-cn.com/problems/remove-duplicate-letters/solution/qu-chu-zhong-fu-zi-mu-by-leetcode-soluti-vuso/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/366fc2c7ca7448bd9b18639a8fcac347.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221005/aebed37372354c3db9fc8d8c874a57d4.png