316. 去除重复字母

难度中等

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

示例 1：

输入：s = "bcabc"

输出："abc"

示例 2：

输入：s = "cbacdcbc"

输出："acdb"

提示：

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

# 贪心 + 单调栈

例如：$bcabc$

$i =0$：$b$ 已经是满足字典序最小

$i=1$：$bc$ 已经是满足字典序最小

$i=2$：发现 $c > a$

• $a$ 后面有 $c$，那么应该是 $ac$ 而不是 $ca$。即：移除 $c$，还剩余 $b$
• 此时 $b > a$，$a$ 后面有 $b$，那么应该是 $ab$ 而不是 $ba$。即：移除 $b$
• 最后的结果集：$a$

$i=3$：$ab$ 已经是满足字典序最小

$i=4$：$abc$ 已经是满足字典序最小

---

例如：$cbacdcbc$

$i=0$：$c$ 已经是满足字典序最小

$i=1$：$c>b$，$b$ 后面含有 $c$，那么应该是 $bc$ 而不是 $cb$。即：移除 $c$，将 $b$ 放入结果集：$b$

$i=2$：$b > a$，$a$ 后面含有 $b$，那么应该是 $ab$ 而不是 $ba$。即：移除 $b$，将 $a$ 放入结果集：$a$

$i=3$：$ac$ 已经是满足字典序最小

$i=4$：$acd$ 已经是满足字典序最小

$i=5$：结果集中含有 $c$，可以贪心的选择前面的，排除当前元素

• $acd > adc$，选择后者则会导致结果集变大

$i=6$：$d > b$，$b$ 后面没有元素 $d$，那么放入结果集：$acdb$

$i=7$：结果集中含有 $c$，可以贪心的选择前面的，排除当前元素

最后的结果集：$acdb$

枚举下标 $i$

• 若栈中元素包含 $s[i]$，那么舍弃 $s[i]$，因为若舍弃栈中元素，则会导致字典序更大
• 若栈顶元素大于 $s[i]$，若 $i$ 后面含有栈顶元素，那么移除栈顶元素，不断地重复此过程直至栈顶元素 $< s[i]$ 或者 $i$ 后面不包含栈顶元素，最后将 $s[i]$ 入栈形成字典序最小
• 若栈顶元素小于 $s[i]$，那么此时已经满足字典序最小，将 $s[i]$ 入栈

设 $idx[i]$ 为元素 $i$ 后面的重复元素的最远下标，采用 $visited[i]$ 数组记录栈中是否包含元素 $i$

class Solution {

    public String removeDuplicateLetters(String s) {

        int n = s.length();

        //i 后面的重复元素的最远下标

        int[] arr = new int[26];

        for (int i = 0; i < n; i++) {

            arr[s.charAt(i) - 'a'] = i;

        }

        // 单调栈

        StringBuilder st = new StringBuilder();

        boolean[] visited = new boolean[26];

        for (int i = 0; i < n; i++) {

            char ch = s.charAt(i);

            int v = ch - 'a';

            if (visited[v]) {

                continue;

            }

            int peek;

            // 栈顶元素大于当前元素 && s [i] 后面包含栈顶元素

            while (st.length() > 0 && (peek = st.charAt(st.length() - 1) - 'a') > v && arr[peek] > i) {

                st.deleteCharAt(st.length() - 1);

                visited[peek] = false;

            }

            visited[v] = true;

            st.append(ch);

        }

        return st.toString();

    }

}