企业官网建设流程全解析

思路：贪心 + 单调栈

要使得结果字典序最小，并且每个字母只出现一次，同时保持原字符串中字符的相对顺序。

1. 统计每个字符最后出现的位置：用于判断当前栈顶字符在之后是否还会出现。
2. 维护一个栈（用 StringBuilder 模拟），表示当前构造的结果字符串。
3. 遍历字符串，对于当前字符 c：
   · 如果 c 已经在栈中（visited 标记），直接跳过。
   · 否则，当栈非空，且栈顶字符 大于 c，并且栈顶字符在当前位置之后还会出现（即 lastIndex[栈顶] > i），就可以把栈顶弹出，以便让 c 放到更前面，得到更小的字典序。
   · 弹出时记得把对应字符的 visited 标记恢复为 false。
   · 最后将 c 入栈，并标记 visited。

这样每个字符最多入栈、出栈一次，时间复杂度 O(n)。

Java 实现

classSolution{publicStringremoveDuplicateLetters(Strings){int[]lastIndex=newint[26];// 每个字符最后出现的下标for(inti=0;i<s.length();i++){lastIndex[s.charAt(i)-'a']=i;}boolean[]visited=newboolean[26];// 字符是否已经在栈中StringBuilderstack=newStringBuilder();// 用 StringBuilder 模拟栈for(inti=0;i<s.length();i++){charc=s.charAt(i);intidx=c-'a';// 如果已经在栈中，跳过if(visited[idx])continue;// 单调栈：弹出比当前字符大、且后面还会出现的栈顶字符while(stack.length()>0){chartop=stack.charAt(stack.length()-1);if(top>c&&lastIndex[top-'a']>i){stack.deleteCharAt(stack.length()-1);visited[top-'a']=false;}else{break;}}// 当前字符入栈stack.append(c);visited[idx]=true;}returnstack.toString();}}

关键点

· lastIndex 数组：记录每个字符最后一次出现的位置，用于判断能否安全弹出栈顶。
· visited 数组：保证每个字符只出现在结果中一次。
· 弹出条件：栈顶字符 > 当前字符，且栈顶字符在后面还会出现，这样才能在不丢失该字符的前提下，让更小的字符排到前面。
· 复杂度：时间 O(n)，空间 O(1)（字母表大小固定为 26，栈最多 26 个字符）。

示例

输入：s = “bcabc”
输出：“abc”

输入：s = “cbacdcbc”
输出：“acdb”

该解法满足字典序最小且不改变字符相对顺序的要求。