Leetcode 去除重复字母

---

✅ 关键点

1. count[] 表示的是“剩余出现次数”，在遍历每个字符时都要执行 count[c - 'a']--;，这是必须的步骤，不管该字符是否已经在栈中；

2. 使用**单调栈（递增的字典序）**维护当前已选字符构成的“局部最优子结果”，最终逆序输出即可得到全局最优结果；

3. 如果当前字符 不在栈中，那么就尝试把它加入栈；

   • 但加入前，有可能需要将字典序更大的字符弹出，让位给当前更小的字符，以满足字典序最小的目标；
   • 弹出操作的前提是：该字符 之后还会出现（通过 count[] 判断）；

4. 弹出时要记得将 inStack[] 标记为 false，加入时则标记为 true，以确保每个字符在栈中只出现一次。

---

✅ 可以这样总结这个“让位逻辑”：

当前字符要想成功“插队”，它必须比栈顶更小，而且栈顶字符不能是“最后一次机会”，这样才有资格被踢出。

---

✍️ 补充一句更直观的通俗解释：

你可以把这个过程类比为“最小字典序的选秀”：

• 每个字符都想进最终的结果队伍（栈）；
• 如果一个新的候选人（当前字符）进来，发现他更“优秀”（字典序更小）；
• 那就要判断当前队伍里的末尾成员是否可以被替换掉：
  • 如果末尾成员 还会在之后出现，就可以被替换；
  • 否则就必须留下他（他已经是唯一一次出现了）；
• 最终构建出的是一支去重后最强（字典序最小）的队伍。

---

java solution

class Solution {
    public String removeDuplicateLetters(String s) {
        //首先需要统计每个字符剩余出现次数
        int[] count = new int[26];
        boolean[] inStack = new boolean[26];
        for(char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        
        //创建单调栈

        Deque<Character> stack = new ArrayDeque<>();

        //然后开始遍历
        for(char c : s.toCharArray()) {
            //首先更新count数组
            int index = c - 'a';
            count[index]--;

            if(inStack[index]) continue;

            while(!stack.isEmpty() && c < stack.peek() && count[stack.peek() - 'a'] > 0) {
                inStack[stack.pop() - 'a'] = false;
            }

            stack.push(c);
            inStack[c - 'a'] = true;
        }

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        
        return sb.reverse().toString();
    }
}

原文地址：https://blog.csdn.net/coldasice342/article/details/147228763

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！