LeetCode每日打卡-316. 去除重复字母

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

示例 1：

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

示例 2：

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

提示：

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

思路
要删除已重复的字符，可以在第一次遍历时查询是否重复，而在生成处理后的字符时，需要能快速找到该字符第一次出现的位置，那么可以在第一次遍历时维护一个HashMap<Character,Integer>。
第一次遍历字符串时，若当前遍历的字符不在map中，将该字符和在字符串中的位置存入map中；已存在map中则不作操作。
第二次遍历字符串时，若当前字符在map中，将该字符保留，并且删除该字符的键值对；若不存在，不作操作。这样就可以得到保留第一次出现的字符。
代码

import java.util.*;

class Solution {
    public String removeDuplicateLetters(String s) {
        int len=s.length();
        if(s==null||len<1){
            return "";
        }

        StringBuffer res=new StringBuffer();

        HashMap<Character,Integer> map = new HashMap<Character,Integer>();



        for(int i=0;i<=len-1;i++){
            if(!map.containsKey(s.charAt(i))){
                map.put(s.charAt(i),i);
            }
        }

        for(int i =0;i<=len-1;i++){
            if(map.containsKey(s.charAt(i))){
                res.append(s.charAt(i));
                map.remove(s.charAt(i),i);
            }
        }

        return res.toString();

    }
}

这样做的话就不能保证返回结果的字典序最小；所以我们需要用到栈

输入 "bcabc"
输出 "bca"
预期结果 "abc"

思路

1. 怎么去重？

用一个vis数组，如果这个字符入栈了，那么我们就把他标记为1，即有这个字符了，当他再出现，我们就不要了，直接跳过；

1. 为了得到最小的字典序，该怎么做？

当一个s[i]>s[i+1]（准确一点应该是栈中前一个数大于后一个数时，类似于单调栈）时，i就可以被弹出去了，但是如果这个s[i]是独苗（后面再没有这个字符了），就不能弹出去了，那么我们用一个num数组存储s中剩余字符的情况，每当我们抛出一个字符或者我们跳过一个数的时候，其数都要减1；

import java.util.Stack;

/**
 * 栈操作 o(n*log(n))
 */
public class Solution {

    public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<>();


        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if (stack.contains(c)) {
                continue;
            }

            //public int indexOf(int ch, int fromIndex): 返回从 fromIndex 位置开始查找指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。
            while (!stack.isEmpty() && stack.peek() > c && s.indexOf(stack.peek(), i) != -1) {
                stack.pop();
            }
            stack.push(c);
        }
        String rs = "";
        for (int i = 0; i < stack.size(); i++) {
            rs += stack.get(i);
        }
        return rs;
    }
}