单调栈的妙用

题目1

题目链接

402. 移掉 K 位数字 - 力扣（LeetCode）

题目大意

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。

请你以字符串形式返回这个最小的数字。

示例

输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

提示

• \(1 <= k <= num.length <= 10^5\)
• num 仅由若干位数字（0 - 9）组成
• 除了 0 本身之外，num 不含任何前导零

思路

• 对于一个数位j，如果它左边的数位i，满足(i > j),那么左边的数位就可以移除了
• 我们对每一个满足上面的要求（i > j）的数位，都执行删除操作，操作k次后得到的数字一定是最小的
• 怎么证明呢？
  • 采用反证法，如果我们对于当前数位j，且左边的数位i，（i > j）
  • ①\(a_1,a_2,a_3,...,a_i,a_j,...\)
  • ②\(a_1,a_2,a_3,...,a_j,...\)​
  • ①表示的是不移除\(a_i\);②表示的是移除\(a_i\)
  • 很显然，由于\(a_i > a_j\)，① > ②
  • 因此，移除一定比不移除要更小
• 想一想，符合这种要求的数据结构，很显然就是单调栈了，而且维护的是单调递增的单调栈

代码

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        st = []
        remain = len(num) - k 
        if remain == 0:
            return '0'
        for x in num:
            while k and st and st[-1] > x:
                st.pop()
                k -= 1
            st.append(x)
        ans = ''.join(st[:remain]).lstrip('0')
        if ans == '':
            return '0'
        return ans

题目2

题目链接

316. 去除重复字母 - 力扣（LeetCode）

题目大意

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。

需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例

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

提示

• \(1 <= s.length <= 10^4\)
• s 由小写英文字母组成

思路

• 思路与上题类似，但多了一个条件——每个字母只出现一次
• 我们在执行移除操作时，需要额外判断当前数 \(x\)​ 是否可以移除?
  • 如果 \(x\)​剩余的次数等于0了，那么就不可以移除
• 如果一个数\(x\)已经在单调栈中出现了，且没有被移除，那么\(x\)​就不可以再次进栈了，直接跳过！
  • 如果再次进入，那么就出现两次了！

代码

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        st = []
        cnt1 = Counter()  # x在st中出现的次数
        cnt2 = Counter(s) # x的
        for x in s:
            if cnt1[x] == 0:
                while st and x < st[-1] and cnt2[st[-1]] > 0:
                    cnt1[st.pop()] -= 1
                st.append(x)
                cnt1[x] += 1
            cnt2[x] -= 1
        return ''.join(st)