316. 去除重复字母(中等)

1，问题描述

316. 去除重复字母

难度：中等

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

示例 1：

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

示例 2：

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

提示：

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

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

2，初步思考

​ 贪心 + 单调栈

3，代码处理

import java.util.ArrayDeque;
import java.util.Deque;

public class _316去除重复字母 {
    
    // 官方解法
    public String removeDuplicateLetters_stack_gov(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        char[] charArray = s.toCharArray();
        int[] dp = new int[26];
        for (char c : charArray) {
            dp[c - 'a']++;
        }

        StringBuilder sb = new StringBuilder(26);
        boolean[] visited = new boolean[26];
        for (char c : charArray) {
            int idx = c - 'a';
            dp[idx]--;
            if (visited[idx]) continue;
            while (!stack.isEmpty() && stack.peekLast() > c && dp[stack.peekLast() - 'a'] > 0) {
                sb.deleteCharAt(sb.length() - 1);
                Character c1 = stack.pollLast();
                visited[c1 - 'a'] = false;
            }
            stack.addLast(c);
            visited[idx] = true;
            sb.append(c);
        }
        return sb.toString();
    }

    // 解法：单调栈+贪心
    public String removeDuplicateLetters_monostone(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        char[] charArray = s.toCharArray();
        int len = charArray.length;
        int[] dpIdx = new int[26];// 最后一个的索引值
        boolean[] visited = new boolean[26];// 记录每个字母是否被访问过
        for (int i = 0; i < len; i++) {
            dpIdx[charArray[i] - 'a'] = i;// 记录每个字母最后出现的位置
        }

        for (int i = 0; i < len; i++) {
            char c = charArray[i];
            if (visited[c - 'a']) continue;
            while (!stack.isEmpty() && stack.peekLast() > c && dpIdx[stack.peekLast() - 'a'] > i) {
                Character c1 = stack.pollLast();
                visited[c1 - 'a'] = false;
            }
            stack.addLast(c);
            visited[c - 'a'] = true;
        }

        StringBuilder stringBuilder = new StringBuilder();
        for (Character c : stack) {
            stringBuilder.append(c);
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        _316去除重复字母 removeDuplicateLetters = new _316去除重复字母();
//        System.out.println(removeDuplicateLetters.removeDuplicateLetters_monostone("bcabc"));
//        System.out.println(removeDuplicateLetters.removeDuplicateLetters_monostone("cbacdcbc"));
        System.out.println(removeDuplicateLetters.removeDuplicateLetters_monostone("ecbacba"));
    }
}