单调栈 - 1081. 不同字符的最小子序列 - 《数据结构与算法》

题目
思路分析

题目

题目来源：力扣（LeetCode）

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

注意：该题与 316 https://leetcode.com/problems/remove-duplicate-letters/ 相同

示例 1：

输入：s = “bcabc”
输出：”abc”

示例 2：

输入：s = “cbacdcbc”
输出：”acdb”

思路分析

首先解释一下两个名词：

字典序：对于字符而言，按 ascii 码值进行比较，小的排在前，大的排在后。对于字符串，从第 0 位字符开始比较，ascii 码数值小的排在前面，如果相同，就延后一位比较 ascii 码值大小。

子序列：子序列不同于子串，子串要求它们在原串中连续，而子序列则不要求连续。例如acd是abcd的子序列，但不是子串。

维护一个单调栈，栈中字符从栈低到栈顶单调递增，也就是按字典序从小到大排列。

遍历字符串 s：

若当前字符已存在于栈中，则不需要执行任何操作，直接继续遍历下一个字符，即如果遍历到栈中已经有的字符，可以舍弃当前遍历到的字符(因为要去除字符串中重复的字母，使得每个字母只出现一次)；
若当前字符在栈中不存在并且栈不为空，则将当前遍历的字符与栈顶字符进行比较(因为要保证返回结果的字典序最小)：
1. 若当前遍历的字符比栈顶字符的 ASCII 值小并且在当前遍历的字符后面还有与此时栈顶字符相同的字符，即 s.indexOf(stack.peek(), i) != -1，则将栈顶字符出栈，直到栈顶字符小于当前遍历的字符并且当前遍历的字符在后面的位置上不再有该字符，那么要将当前遍历的新字符入栈；
2. 若是当前遍历的字符比栈顶字符的ASCII 值大，则直接将当前遍历的新字符入栈。 ```javascript 示例：s = “bcabc”
i = 0，s[i] = ‘b’，stack 为空，’b’ 进栈 -> stack：[b]
i = 1，s[i] = ‘c’，不在栈中且 ‘b’ < ‘c’，’c’ 进栈 -> stack：[b, c]
i = 2，s[i] = ‘a’，不在栈中且 ‘c’ > ‘a’ 并且 ‘a’ 的后面还有 ‘c’，’c’ 出栈；
```
         'b' > 'a' 并且 'a' 的后面还有 'b'，'b' 出栈 'a' 进栈 -> stack：[a]
```
i = 3，s[i] = ‘b’，不在栈中且 ‘a’ < ‘b’，’b’ 进栈 -> stack：[a, b]
i = 4，s[i] = ‘c’，不在栈中且 ‘b’ < ‘c’，’c’ 进栈 -> stack：[a, b, c]


**代码**
```javascript
/**
 * @param {string} s
 * @return {string}
 */
// 字典序：
// 对于字符而言，按 ascii 码值进行比较，小的排在前，大的排在后。
// 对于字符串，从第 0 位字符开始比较，ascii 码数值小的排在前面，如果相同，就延后一位比较 ascii 码值大小
var smallestSubsequence = function (s) {
  let arr = [];
  for (let i = 0; i <= s.length - 1; i++) {
    let str = s[i]
    // 当前遍历的字符已经在栈中，则不需执行任何操作，继续遍历下一个字符
    if (arr.includes(str)) continue;
    // arr[arr.length - 1] > str 判断栈顶字符是否大于当前遍历的字符
    // s.indexOf(arr[arr.length - 1], i) > i 判断栈顶的字符在字符串后面的位置上是否还有该字符
    // 如果栈顶字符比当前遍历的字符大，并且栈顶的字符在字符串后面的位置上还有该字符，则将栈顶字符出栈
    // 直到栈为空或者栈顶字符小于当前遍历的字符，那么将当前遍历的字符入栈
    while (arr.length > 0 && arr[arr.length - 1] > str &&
      s.indexOf(arr[arr.length - 1], i) > i) {
      arr.pop()
    }
    // 栈为空或者栈顶字符小于当前遍历的字符，将当前遍历的字符入栈
    arr.push(str)
  }
  return arr.join("")
};