@SomeBottle 在 Leetcode每日一题 —— 1081. 不同字符的最小子序列 中发帖
思路
题目要求:
找的是子序列,不是连续子序列;
要求子序列字典序尽量小;
子序列包含出现的所有字符。
看到第 3 点能想到用哈希表来进行记录;从前两点看来,因为字符可能会重复出现,在处理过程中我们可能会丢掉一些重复出现的字符,使得最终字典序小的字符尽量出现在子序列前面。
可以用栈来处理。从左至右扫描字符串,如果栈顶字符在字典序上大于当前扫描到的字符,且这个栈顶字符在后面还有出现,就弹出栈顶,直至栈顶 \le 当前字符。
“字符在后面还有出现”就可以用哈希表来记录每个字符的出现次数并动态更新了,为了防止重复把已经在栈中的字符加入栈,还需要用另一个表记录字符是否被使用。
代码
class Solution {
public:
string smallestSubsequence(string s) {
// 要求包含所有出现的不同字符
...