316. 去除重复字母

316. 去除重复字母

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同

示例 1：

输入：s = "bcabc"
输出："abc"

示例 2：

输入：s = "cbacdcbc"
输出："acdb"

提示：

• 1 <= s.length <= 10<sup>4</sup>
• s 由小写英文字母组成

此题主要考察的是栈的使用，栈的数据结构特点是后进先出。
下面介绍官方解法：

public  String removeDuplicateLetters(String s) {
        int length = s.length();
        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        int[] indexes = new int[26];
        for (int i = 0; i < length; i++) {
            indexes[chars[i] - 'a'] = i;
        }
        boolean[] visited = new boolean[26];
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < length; i++) {
            char c = chars[i];
            if (visited[c-'a']) {
                continue;
            }
            while (!stack.isEmpty() && stack.peekLast() > c && indexes[stack.peekLast()- 'a'] > i) {
                Character character = stack.removeLast();
                visited[character - 'a'] = false;
            }
            stack.addLast(c);
            visited[c - 'a'] = true;
        }
        for (Character c:
             stack) {
            sb.append(c);
        }
        return sb.toString();
    }

大概讲一下思路：
1.记录各个字母最后出现的位置
2.循环遍历，当遍历到的字母比栈顶的字母还要小并且后续还可能出现栈顶的字母时则将栈顶字母移除。直到栈中没有符合条件的字母为止。
3.拼接栈中的字母。

参考链接：https://leetcode-cn.com/problems/remove-duplicate-letters/