(LeetCode 每日一题)3170. 删除星号以后字典序最小的字符串(贪心+栈)

题目：3170. 删除星号以后字典序最小的字符串

思路：贪心+栈，时间复杂度0(n)。
对于每一个‘ * ’，优先选最右边的最小字符，才会使最终得到的字符串最小。
用栈，来记录每个字符的位置下标。细节看注释。

C++版本：

class Solution {
public:
    string clearStars(string s) {
    	// 栈，记录已遍历过的每个字符的下标
        stack<int> st[26];
        for(int i=0;i<s.size();i++){
            if(s[i]!='*'){
                st[s[i]-'a'].push(i);
                continue;
            }
            // 贪心，找到最小的字符来删除
            for(auto &x:st){
                if(x.size()>0){
                	// 标记为'*'，表示删除
                	// 选最大的下标值，也就是最后入栈的
                    s[x.top()]='*';
                    x.pop();
                    break;
                }
            }
        }
        //剩余非'*'的就是答案
        string ans="";
        for(int i=0;i<s.size();i++){
            if(s[i]=='*') continue;
            ans.push_back(s[i]);
        }
        return ans;
    }
};

JAVA版本：

class Solution {
    public String clearStars(String s) {
        List<Integer>[] st=new ArrayList[26];
        Arrays.setAll(st,i->new ArrayList<>());
        char[] c=s.toCharArray();
        for(int i=0;i<c.length;i++){
            if(c[i]!='*'){
                st[c[i]-'a'].add(i);
                continue;
            }
            for(var x:st){
                if(x.size()>0){
                    c[x.removeLast()]='*';
                    break;
                }
            }
        }
        int top=-1;
        for(int i=0;i<c.length;i++){
            if(c[i]=='*') continue;
            c[++top]=c[i];
        }
        return new String(c,0,top+1);
    }
}

Go版本：

func clearStars(s string) string {
    c:=[]byte(s)
    st:=make([][]int, 26)
    for i:=0;i<len(s);i++ {
        if s[i]!='*' {
            st[s[i]-'a']=append(st[s[i]-'a'],i)
            continue
        }
        for j,x:= range st {
            if m:=len(x); m>0 {
                c[x[m-1]]='*'
                st[j]=x[:m-1]
                break
            }
        }
    }
    var ans []byte
    for i:=0;i<len(s);i++ {
        if c[i]!='*' {
            ans=append(ans,c[i])
        }
    }
    return string(ans)
}