leetcode 316. 去除重复字母【单调栈官方题解补充：为何要判断栈中是否有当前元素】

超、凢脫俗 2022-10-22 07:47 119阅读 0赞

class Solution { 
    public:
        
        string removeDuplicateLetters(string s) { 
            vector<int> last(26,0);
            for(int i=0;i<s.size();i++){ 
                last[s[i]-'a'] = i;
            }
    
            stack<char>st;
            string ret = "";
            vector<bool> inst(26,0);
    
            for(int i=0;i<s.size();i++){ 
                int c = s[i];
                if( inst[c-'a']){ 
                    continue;
                }
    
                while( !st.empty() ){ 
                    char top = st.top();
                    if( last[ top-'a' ] >= i && c <= top){ 
                        st.pop();
                        inst[top-'a'] = 0;
                    }else{ 
                        break;
                    }
                }
                
                st.push(c);
                inst[c-'a'] =1;
            }
            while(!st.empty()){ 
                char c = st.top();
                st.pop();
                ret = string(1,c) + ret;
            }
            return ret;
        }
    };

在不去重的时候，就是栈中的元素有的时候也进行pop会有什么后果
    输入
    "acfadcf"
    输出
    "adcf"
    预期结果
    "acdf"
    
    这一个样例，acf入栈之后，当前遇到第二个a，
    如果不看栈里面是不是有a，就直接弹栈的话
    这个时候就会把acf都弹出来，因为acf现在还有剩余的容量，
    我们想的是，a（第二个）在栈顶遇到了f，后面出现过f，那么就可以把f弹出来，
    但是如果栈中有a，如果你现在弹出来的f之后，就必须保证，
    第二个a和后面的f区间的字串，比当前栈中的字串的字典序小
    而这个是无法保证的，比如上面这个例子，把acf全部弹出去之后，后面的acdf的字典序比adcf大
    所有正确的做法应该是跳出这个a，后面的字串能否比当前的字典序小，应该让后面的字串逐一判断
    而不是在遇到a的时候就决定                                                                                                                                                                                                                                                                                                                                                                                                                                                    
    
    正确的样例：
    
    输入
    
    "acfadcf"
    输出
    "acdf"
    预期结果
    "acdf"

![在这里插入图片描述][20210405152102230.png]

[20210405152102230.png]: /images/20221022/f3164399bf0048fd8567d58ef74a52a8.png