链接
https://leetcode.cn/problems/remove-duplicate-letters/description/
思路
这个题并不是传统的单调栈,所以硬套单调栈会懵逼。
什么时候用单调栈? 这个题目要求去除重复字母,还要保持字典序。 注意,跟相对顺序相关的题目,如:其后比他大的第一个元素,其后比他小的第一个元素,再比如保持字典序的题目,都适合用单调栈。
应用单调栈我们要想清楚的核心问题是:
1. 什么情况下我们弹栈。
2. 栈内元素是(部分)升序还是(部分)降序
3. 我们应该从前往后遍历,还是从后往前遍历
在这个题目中,我们要的是保持字典序,即我们要的最后的序列是升序序列。所以我们解答了第二个核心问题,即我们要的是升序。
在这个题目中,还有个条件是让我们去除重复字母。我们要的是升序,所以可能要把比较大的字母弹栈。比较大的字母越早被弹栈,我们越能保持字典序。(举个例子,dabd,我们应该让第一个d弹栈),所以我们应该从前往后遍历。
在这个题目中,我们弹栈也有两种情况。 既然我们要保持字典序,那应该栈顶元素大于待入栈元素时弹栈,但并不是每次都这样操作。因为如果栈顶元素没有出现在剩余的未遍历序列中,我们就不能再弹了,再弹我们就漏字母了,所以这里要加一个判断。
代码
class Solution: def removeDuplicateLetters(self, s: str) -> str: # visited为True表示该字母已经加入单调栈中了 visited = [False for i in range(26)] # remains代表当前未遍历到的字母的计数(<=0代表未遍历到的序列中没有这个字母了) remains = [0 for i in range(26)] single_stack = [] # 初始化remains for i in s: idx = ord(i) - ord('a') remains[idx] += 1 for i in s: if not visited[ord(i)-ord('a')]: # 如果这个字符没有加入到单调栈中 while single_stack and ord(single_stack[-1]) > ord(i): idx = ord(single_stack[-1])-ord('a') if remains[idx] > 0: # 还有剩余的大字符, 影响字典序,弹栈并且重置加入单调栈的状态 visited[idx] = False single_stack.pop() # 必须要有else, 否则remains[idx]没有剩余数值时,单调栈不弹栈, 会陷入死循环 else: break # 别管有没有弹栈, 当前字母都得入栈, 跟其他单调栈的题目没啥区别 single_stack.append(i) # 入单调栈了, 自然是要更新visited记录 visited[ord(i) - ord('a')] = True # remains是剩余序列的计数, 已经遍历过当前字母了, 所以要减1 remains[ord(i)-ord('a')] -= 1 return ''.join(single_stack)
标签:弹栈,遍历,remains,字母,316,去除,ord,单调 From: https://www.cnblogs.com/bjfu-vth/p/17748211.html