栈
解题思路
-
什么是字典序：从字符串的 起始位置 比较 ASCII 码值，如果小的，字典序就在前面；
- 例如 abc 的字典序就在 acb 之前，记作：
abc < acb - 如果从左至右遍历到的字符的字典序依次上升，那么该字符串已经字典序最小
- 例如 abc 的字典序就在 acb 之前，记作：
-
图解
![]( "去除重复字母")
复杂度
-
时间复杂度：
O(n)- 统计字符串中出现过的字母在字符串中出现的最后位置，需要对字符串浏览一遍，时间复杂度为
O(n)； - 扫描字符串一遍，得到结果，时间复杂度为
O(n)；
- 统计字符串中出现过的字母在字符串中出现的最后位置，需要对字符串浏览一遍，时间复杂度为
-
空间复杂度：
O(1)，使用栈来存储结果字符串（最大长度为26）以及其他辅助变量，均为常数级的变量空间；
代码实现
var removeDuplicateLetters = function (s) {
// 1. 声明栈，用于存储字典序
const stack = [];
// 2. 声明一个 hash 数组，用于记录 stack 中存储的字符
const visited = new Array(26).fill(false);
// 3. 声明一个 hash 数组，用于记录字符最后出现的位置
const lastInx = new Array(26).fill(0);
const asset = 'a'.charCodeAt(0); // 偏移量
for (let i = 0; i < s.length; i++) {
lastInx[s[i].charCodeAt(0) - asset] = i;
}
// 4. 从左到右扫描字符串，寻找不重复的最小字典序
for (let i = 0; i < s.length; i++) {
// 4-1. 若当前字符已经在栈中，⽆需处理
if (visited[s[i].charCodeAt(0) - asset]) continue;
// 4-2. 若当前字符不在栈中：入栈前需要比较栈内元素是不是 最小字典序
// - 栈不为空 && 栈顶元素 > 当前字符 && 栈顶字符在后续字符串还会出现
// - 则说明之后会出现更小的字典序，需要出栈栈顶元素
// - 直到栈为空或栈顶字符比当前字符小，或栈顶字符在当前位置之后不会再出现
while (stack.length && stack[stack.length - 1] > s[i] && lastInx[stack[stack.length - 1].charCodeAt(0) - asset] > i) {
visited[stack.pop().charCodeAt(0) - asset] = false; // 更新栈中存在的元素
}
// 4-3. 入栈当前字符，并更新 栈中存在的元素
stack.push(s[i]);
visited[s[i].charCodeAt(0) - asset] = true;
}
return stack.join('');
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 559. N 叉树的最大深度
上一篇
评论
