LeetCode-316-mid-去除重复字母（单调栈）

关键字：“单调栈”

题目描述

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

LeetCode-316-mid-去除重复字母

分析

题目要求：

去重且每个字母出现一次：则返回结果的长度固定
返回结果的排列保持原有相对位置
返回结果的字典序最小

设s中每个字母出现次数为 $[c_a, c_b,..., c_z]$ ,则满足条件1和2的排列顺序总共有： $c_a\times c_b \times ... \times c_z$ 种，由于输入规模较大，暴力枚举的方法不可行。

解题思路

条件2和尽量字典序的条件3：-> 单调栈（有相对位置+一定顺序）

目前还没有理清之间的关系。单调栈的性质和与这道题的联系。

目标是条件3：尽量把字典序小的字符（'a','b','c',...,'z'）排在前边。所以可以尽量按照字典序升序的单调栈来排列。如果遇到原打算删除的字符在剩余字符串中不存在，则保留该字符。

设已有字符串pre,当前字符c,剩余字符串post。

如果c没有出现在pre中，则将c放入pre中(并将pre中最邻近结尾且大于c的在post中仍然存在的字符删除）// 这里是c字符所在位置要尽可能放在满足其字典序的位置，操作后所能形成的字典序更小。要求可删除的字符要在post字符串中出现，这样才能在剩余字符串中将该删除的字符附在最终形成的字符串的末尾。

如果c已经出现在pre中，则查看下一字符。（如果将pre中的c去掉，则使得字典序变大)

算法

INPUT: s
OUTPUT: ans
INIT:
visit[26], count[26]
for c in s :
    count[c-'a'] ++ 

//循环不变量：visit, count, stack
stack
for c in s :
    // 现有stack中没有c
    if visit[c] == false :
        while !stack.empty() && stack.top() > c && count[stack.top()-'a'] > 0 )
            visit[ stack.top() ] = false
            stack.pop()
        stack.push( c )
        visit[c-'a'] = true 
    count[c-'a'] -- 

ans = string(stack)
return ans

数据结构

记录访问信息：数组、vector

模拟单调栈：string、stack

复杂度分析

空间复杂度 $O(n)$

时间复杂度 $O(n)$ ,不考虑stack.pop()

代码实现


class Solution {
public:
    string removeDuplicateLetters(string s) {

        vector<int> visit(26), count(26) ;
        for ( char c : s ){
            ++ count[c-'a'] ;
        }

        string stk = "" ;
        for ( char c : s ){
            if ( visit[c-'a'] == 0 ){
                while ( !stk.empty() && stk.back() > c && count[stk.back()-'a'] > 0 ){
                    visit[ stk.back()-'a' ] = 0 ;
                    stk.pop_back() ;
                }
                stk.push_back( c ) ;
                visit[c-'a'] = 1 ;
            }
            -- count[c-'a'] ;

        }
        return stk ;
    }
};

使用vector或数组来存储对字符信息的访问，时间复杂度更低
单调栈访问中，每个元素至少入栈一次