316. 去除重复字母/c++

316. 去除重复字母 - 力扣（LeetCode）

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

示例 1：

输入：s = "bcabc"输出："abc"

示例 2：

输入：s = "cbacdcbc"输出："acdb"

题解---使用单调栈 + 贪心

class Solution { public: string removeDuplicateLetters(string s) { vector<int> lastIndex(26, -1); for (int i = 0; i < s.size(); ++i) { lastIndex[s[i] - 'a'] = i; // 记录最后出现位置 } vector<bool> inStack(26, false); string stack = ""; // 用 string 模拟栈 for (int i = 0; i < s.size(); ++i) { char c = s[i]; // 如果已经在结果中，跳过 if (inStack[c - 'a']) continue; // 如果栈非空，且栈顶 > 当前字符，且栈顶后面还会出现 → 弹出 while (!stack.empty() && stack.back() > c && lastIndex[stack.back() - 'a'] > i) { inStack[stack.back() - 'a'] = false; stack.pop_back(); } // 加入当前字符 stack.push_back(c); inStack[c - 'a'] = true; } return stack; } };