去除重复字母（316）

题目

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

示例

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

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

提示

• 1 <= s.length <= 104
• s 由小写英文字母组成

算法

贪心 + 栈

字典序：就是按照字母在字典中出现的顺序，比如a, b, c, ... , z的顺序

题目要求字典序最小就是指让返回结果的字母顺序尽量按照字典顺序出现

为了让字典序最小，我们可以贪心的让较大的字母尽可能地出现的后面

我们维护一个数组letters存储每个字幕出现的次数，每推入一个字母时，对应位置的数字-1，用来表示当前位置之后每个字母出现的次数

我们维护一个数组canPush用来表示当前字母能否被推入数组，初始全部为true，当一个字母被推入栈中时，我们将其对应位置的值改为false表示之后不能再推入数组；如果我们可以让字典序变得更小而要弹出已经入栈的字母，我们在弹出栈的同时将这个位置的值改为true，表示之后遍历到该字母时可以推入栈

现在的问题是如何让字典序最小：因为我们需要让较大的字母尽可能出现在后面，所以当我们将要入栈的元素小于栈顶元素时而且在将要入栈元素后面还会出现栈顶元素时，我们就弹出栈顶元素并将canPush对应位置改为true，这个判断直到栈为空或者栈顶元素不在大于将要入栈元素或者栈顶元素不会在之后出现的情况下停止，然后我们将当前要入栈的元素推入栈并将canPush对应位置改为false

我们每遍历过一个元素就需要将letters对应位置的值-1，以便我们可以判断当前位置后面每个字母还会出现多少次

最后的结果就是栈中从栈底到栈顶的元素拼接的值

export const removeDuplicateLetters = (s) => {
	const letters = new Array(26).fill(0);
	const canPush = new Array(26).fill(true);
	const stack = [];
	Array.prototype.forEach.call(s, (t) => letters[t.charCodeAt() - 97]++);
	Array.prototype.forEach.call(s, (t) => {
		if (canPush[t.charCodeAt() - 97]) {
			while (stack.length && stack[stack.length - 1] > t) {
				if (letters[stack[stack.length - 1].charCodeAt() - 97]) {
					canPush[stack[stack.length - 1].charCodeAt() - 97] = true;
					stack.pop();
				} else {
					break;
				}
			}
			stack.push(t);
			canPush[t.charCodeAt() - 97] = false;
		}
		letters[t.charCodeAt() - 97]--;
	});
	return stack.join("");
};