1081. 不同字符的最小子序列【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 单调栈 + 贪心
• 3. 🔗 引用

1. 📝 题目描述

• leetcode

返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。

子序列 是可以通过从另一个数组删除或不删除某些元素，但不更改其余元素的顺序得到的数组。

---

示例 1：

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

示例 2：

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

---

提示：

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

---

注意：该题与 316. 去除重复字母 相同

2. 🎯 s.1 - 单调栈 + 贪心

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {string} s
 * @return {string}
 */
var smallestSubsequence = function (s) {
  const last = new Array(26).fill(0)
  for (let i = 0; i < s.length; i++) last[s.charCodeAt(i) - 97] = i
  const inStack = new Array(26).fill(false)
  const stack = []
  for (let i = 0; i < s.length; i++) {
    const c = s.charCodeAt(i) - 97
    if (inStack[c]) continue
    while (
      stack.length &&
      stack[stack.length - 1] > c &&
      last[stack[stack.length - 1]] > i
    ) {
      inStack[stack.pop()] = false
    }
    stack.push(c)
    inStack[c] = true
  }
  return stack.map((c) => String.fromCharCode(c + 97)).join('')
}

• 时间复杂度：$O(n)$，其中 $n$ 是字符串的长度
• 空间复杂度：$O(1)$，栈和辅助数组大小不超过 26

算法思路：

• 记录每个字符的最后出现位置
• 维护单调递增栈，若当前字符小于栈顶且栈顶字符后面还会出现，则弹出栈顶
• 通过 inStack 标记避免重复入栈，保证每个字符恰好出现一次

3. 🔗 引用

• 316. 去除重复字母