1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public String removeDuplicateLetters(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        char[] sArray = s.toCharArray();
        int[] lastIdx = new int[26];
        for (int i = 0; i < sArray.length; i++) {
            char currChar = sArray[i];
            lastIdx[currChar - 'a'] = i;
        }
        boolean[] visited = new boolean[26];
        for (int i = 0; i < sArray.length; i++) {
            if (visited[sArray[i] - 'a']) {
                continue;
            }
            while (!stack.isEmpty() && sArray[i] < stack.peek() && lastIdx[stack.peek() - 'a'] > i) {
                visited[stack.pop() - 'a'] = false;
            }
            stack.push(sArray[i]);
            visited[sArray[i] - 'a'] = true;
        }
        StringBuilder ans = new StringBuilder();
        while (!stack.isEmpty()) {
            ans.append(stack.pollLast());
        }
        return ans.toString();
    }
}

这道题其实不是很好想.

可以这么想:
我们遍历s的时候, 到达一个位置, 我们就会想这个位置的char是否要包含进来呢? 如果后面这个char不再出现, 那么它此时必须包含. 如果后面还会出现, 那么我们就要看这个char后面的char是否比自己大. 如果比自己大, 那么如果此时不包含该char, 那么更大的char会接替自己的位置, 此时的order一定会比我们保留我们的char要大. 如果后面的和自己一样, 那么保留谁都一样, 我们就保留当前的. 如果后面的比自己小, 由于此时后面还有我们的char, 那么此时如果我们不包含当前的char而是让后面的char接替我们的位置, 此时形成的char肯定会更小, 因此应该让位. 你可能会问, 万一我们到下一个位置, 在该位置时我们决定不包含该char的时候, 那么之前接替位置的char不就被移走了? 不必担心, 因为如果下一个位置的char我们决定也被移除, 那么就说明它之后有更小的char接替它的位置. 因此我们移走一个char的时候肯定是找好接替人了. 我们按照这个逻辑一直走即可. 但是有个重要条件我们落了, 那就是不能有重复的char. 那么如果之后我们到某个位置发现该位置的char之前已经出现过了, 此时的char我们就直接跳过, 这是因为之前出现的char后面的char比它大, 当时决定保留那个char而非我们现在的char. 当然也有可能我们前一个char和我们自己相同, 这我们之前也有讨论, 是保留哪一个都行, 我们选择保留之前的那个.

综上, 一个char如果后面有比自己小的char, 并且比自己小的char之后还有自己出现, 那么此时自己的位置应该让给更小的char去坐.

看代码来感受具体的逻辑. 15行的while循环很重要.

时间复杂度: O(n) 每个位置的char最多进一次出一次栈.
空间复杂度: O(n) 因为用了栈.