LeetCode 316. 去除重复字母

Categories:

题目描述
思路分析
1. 解法一：单调栈 + 贪心（推荐）
相似题目

题目描述

✅ 316. 去除重复字母

思路分析

解法一：单调栈 + 贪心（推荐）

核心思路：

维护一个单调递增的字符栈，保证结果字典序尽量小。

用 lastIndex 数组记录每个字母在字符串中最后出现的位置。

用 inStack 数组标记某个字母是否已在栈中，避免重复入栈。

遍历字符串，对于当前字符 c：

若 c 已在栈中，直接跳过。

否则，循环检查栈顶字母：若栈顶字母 > c（字典序更大），且该栈顶字母在后续还会出现（lastIndex[top] > i），则将栈顶弹出（可以更晚再加入）。

将 c 压栈，标记已在栈中。

最终栈中元素从底到顶即为字典序最小的结果。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串的长度，每个字符最多入栈和出栈各一次。

空间复杂度：O(1)，栈和辅助数组的大小均不超过字符集大小 26。

class Solution {
    public String removeDuplicateLetters(String s) {
        // 记录每个字母最后出现的下标
        int[] lastIndex = new int[26];
        for (int i = 0; i < s.length(); i++) {
            lastIndex[s.charAt(i) - 'a'] = i;
        }

        // 标记字母是否已在栈中
        boolean[] inStack = new boolean[26];
        Deque<Character> stack = new ArrayDeque<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 已在栈中则跳过，避免重复
            if (inStack[c - 'a']) {
                continue;
            }
            // 若栈顶字母大于当前字母，且栈顶字母后续还会出现，则弹出
            while (!stack.isEmpty()
                    && stack.peek() > c
                    && lastIndex[stack.peek() - 'a'] > i) {
                char top = stack.pop();
                inStack[top - 'a'] = false;
            }
            // 当前字母入栈
            stack.push(c);
            inStack[c - 'a'] = true;
        }

        // 栈底到栈顶构成结果（Deque 中栈顶在头部，需逆序）
        StringBuilder sb = new StringBuilder();
        for (char ch : stack) {
            sb.append(ch);
        }
        return sb.reverse().toString();
    }
}

func removeDuplicateLetters(s string) string {
    // 记录每个字母最后出现的下标
    lastIndex := [26]int{}
    for i := 0; i < len(s); i++ {
        lastIndex[s[i]-'a'] = i
    }

    // 标记字母是否已在栈中
    inStack := [26]bool{}
    stack := []byte{}

    for i := 0; i < len(s); i++ {
        c := s[i]
        // 已在栈中则跳过，避免重复
        if inStack[c-'a'] {
            continue
        }
        // 若栈顶字母大于当前字母，且栈顶字母后续还会出现，则弹出
        for len(stack) > 0 && stack[len(stack)-1] > c && lastIndex[stack[len(stack)-1]-'a'] > i {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            inStack[top-'a'] = false
        }
        // 当前字母入栈
        stack = append(stack, c)
        inStack[c-'a'] = true
    }

    return string(stack)
}

相似题目

题目	难度	考察点
1081. 不同字符的最小子序列	中等	单调栈 / 贪心（与本题完全相同）
402. 移掉 K 位数字	中等	单调栈 / 贪心
321. 拼接最大数	困难	单调栈 / 贪心
456. 132 模式	中等	单调栈 / 枚举
496. 下一个更大元素 I	简单	单调栈 / 哈希表
503. 下一个更大元素 II	中等	单调栈 / 循环数组

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/78861367