LeetCode-316

题目

结果

代码

StringBuilder

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - 'a']++;
        }

        boolean[] in = new boolean[26];
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!in[ch - 'a']) {
                while (!sb.isEmpty() && sb.charAt(sb.length() - 1) > ch) {
                    if (cnt[sb.charAt(sb.length() - 1) - 'a'] > 0) {
                        in[sb.charAt(sb.length() - 1) - 'a'] = false;
                        sb.deleteCharAt(sb.length() - 1);
                    } else {
                        break;
                    }
                }
                in[ch - 'a'] = true;
                sb.append(ch);
            }
            cnt[ch - 'a']--;
        }
        return sb.toString();
    }
}

Stack

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - 'a']++;
        }

        boolean[] in = new boolean[26];
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!in[ch - 'a']) {
                while (!stack.isEmpty() && stack.peek() > ch) {
                    if (cnt[stack.peek() - 'a'] > 0) {
                        in[stack.peek() - 'a'] = false;
                        stack.pop();
                    } else {
                        break;
                    }
                }
                stack.push(ch);
                in[ch - 'a'] = true;
            }
            cnt[ch - 'a']--;
        }
        
        StringBuilder sb = new StringBuilder();
        for (char ch : stack) {
            sb.append(ch);
        }
        return sb.reverse().toString();
    }
}

复杂度

时间复杂度：O（n）

空间复杂度：O（1）