c语言数组去掉重复元素，贪心+单调栈——去除重复字母(Leetcode 316)

题目选自Leetcode 316

第一步当然是好好读题~ 有的人读着很快啊，啪 一下

哦原来就是个排序 哒哒哒一分钟解决战斗，欸 怎么全错了。

c语言数组去掉重复元素。再仔细一看，原来少了重要的条件——要求不能打乱其他字符的相对位置！

显然直接排序是不满足了。

思路详解：

思路与算法

c语言fscanf？首先考虑一个简单的问题：给定一个字符串 ss，如何去掉其中的一个字符ch，使得得到的字符串字典序最小呢？答案是：找出最小的满足 s[i]>s[i+1] 的下标 i，并去除字符 s[i]。为了叙述方便，下文中称这样的字符为「关键字符」。

在理解这一点之后，就可以着手本题了。一个直观的思路是：我们在字符串 s 中找到「关键字符」，去除它，然后不断进行这样的循环。但是这种朴素的解法会创建大量的中间字符串，我们有必要寻找一种更优的方法。

我们从前向后扫描原字符串。每扫描到一个位置，我们就尽可能地处理所有的「关键字符」。假定在扫描位置 s[i−1] 之前的所有「关键字符」都已经被去除完毕，在扫描字符 s[i] 时，新出现的「关键字符」只可能出现在 s[i] 或者其后面的位置。

于是，我们使用单调栈来维护去除「关键字符」后得到的字符串，单调栈满足栈底到栈顶的字符递增。如果栈顶字符大于当前字符 s[i]，说明栈顶字符为「关键字符」，故应当被去除。去除后，新的栈顶字符就与 s[i]s[i] 相邻了，我们继续比较新的栈顶字符与 s[i] 的大小。重复上述操作，直到栈为空或者栈顶字符不大于 s[i]。

重复的英文、我们还遗漏了一个要求：原字符串 s 中的每个字符都需要出现在新字符串中，且只能出现一次。为了让新字符串满足该要求，之前讨论的算法需要进行以下两点的更改。

在考虑字符 s[i] 时，如果它已经存在于栈中，则不能加入字符 s[i]。为此，需要记录每个字符是否出现在栈中。

在弹出栈顶字符时，如果字符串在后面的位置上再也没有这一字符，则不能弹出栈顶字符。为此，需要记录每个字符的剩余数量，当这个值为 00 时，就不能弹出栈顶字符了。

解题代码：

c语言去掉数组中重复的元素。 

class Solution {
public:string removeDuplicateLetters(string s) {vector<int> vis(26), num(26);for (char ch : s) {num[ch - 'a']++;}string stk;for (char ch : s) {if (!vis[ch - 'a']) {while (!stk.empty() && stk.back() > ch) {if (num[stk.back() - 'a'] > 0) {vis[stk.back() - 'a'] = 0;stk.pop_back();} else {break;}}vis[ch - 'a'] = 1;stk.push_back(ch);}num[ch - 'a'] -= 1;}return stk;}
};