单调栈解定长最小字典序问题

发表于 分类于 阅读次数： 本文字数： 2.9k 阅读时长 ≈ 5 分钟

其中 1673 和 402、 1081 和 316 题只是换了说法而已，所以这里只有三道题。

  • 316 去除重复字母（困难）
  • 321 拼接最大数（困难）
  • 402 移掉 K 位数字（中等）
  • 1081 不同字符的最小子序列（中等）
  • 1673 找出最具竞争力的子序列（中等）

402. 移掉K位数字

题目描述：

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

注意:

  • num 的长度小于 10002 且 ≥ k。
  • num 不会包含任何前导零。

示例 1 :

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

示例 2 :

1
2
3
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 :

1
2
3
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。

原理解析：

贪心算法：

对于两个相同长度的数字序列，最左边不同的数字决定了这两个数字的大小。

例如，对于 A = caxxx，B = cbxxx，如果 a > b 则 A > B。

基于此，我们可以知道，若要使得剩下的数字最小，需要保证靠前的数字尽可能小。

单调栈：

首先我们需要知道栈的特点，就是先进先出，这个特性保证剩下的数字的有序性。

使用栈这样的数据结构，且当栈顶的元素小于当前元素才能进栈，否则弹出栈顶的元素。

这样保证了栈底的元素是最小的

基于此，我们知道使用单调栈得到的数字字典序最小，但是可能剩余长度不满足要求

最大弹出数：为保证剩余长度满足要求，这里有一个栈总体的最大弹出数字的要求，最多能弹出K次。

逻辑与伪代码

1
2
3
4
5
6
for 当前元素 in 序列:
    while 剩余弹出次数 > 0 and 栈 != null and 栈顶元素 > 当前元素:
        栈.pop()
        剩余弹出次数 -= 1
    栈.add(当前元素)
return 栈[:需要的长度]
  1. 自左至右准备将当前元素存入栈中。
  2. 如果栈顶元素大于当前元素且当前可弹出次数> 0，则弹出栈顶元素，
  3. 重复步骤2，直至不满足步骤2条件。
  4. 将当前元素存入栈中。
  5. 回到步骤1。

动画解析

Python代码

1
2
3
4
5
6
7
8
9
10
class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        res = []
        remain = len(num) - k
        for n in num:
            while k and res and res[-1] > n:
                res.pop()
                k -= 1
            res.append(n)
        return ''.join(res[:remain]).lstrip('0') or '0'

注意要点

  1. 在判断栈顶元素是否大于当前进栈元素时，要先判断栈是否为空，否则会有空指针异常。
  2. 在结果输出时要注意输出的长度和栈为空时的输出值。

316. 去除重复字母

题目描述

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例 1：

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

示例 2：

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

提示：

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

原理解析

最大弹出数：为保证剩余每个字母都出现一次，需要统计每个字母的最大弹出数，使用哈希表来存储。

每个字母只出现一次：保证每个字母在栈中只出现一次，可以使用一个哈希表来存储栈中的对应元素。

逻辑与伪代码

1
2
3
4
5
6
7
for 当前元素 in 序列:
    if 当前元素 not in 栈:
        while 栈顶元素剩余弹出次数 > 1 and 栈 != null and 栈顶元素 > 当前元素:
            栈.pop()
        栈.add(当前元素)
    当前元素剩余弹出次数 -= 1
return 栈[:需要的长度]

Python代码

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        remain_count = collections.Counter(s)
        for c in s:
            if c not in stack:
                while stack and c < stack[-1] and remain_count[stack[-1]] > 0:
                    stack.pop()
                stack.append(c)
            remain_count[c] -= 1
        return ''.join(stack)

321. 拼接最大数

题目描述

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

示例 1:

1
2
3
4
5
6
输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:
[9, 8, 6, 5, 3]

示例 2:

1
2
3
4
5
6
输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]

示例 3:

1
2
3
4
5
6
输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]

原理解析

单调栈一分为二：两个单调栈的长度之和为合成的数组长度k，分别对两个数组进行上述两题的操作，获取两个单调栈。

将两个单调栈合并得到最终结果，对比不同的单调栈长度分配方法，获得最优的结果

使用归并排序中的merge() 方法来合并，两个单调栈

动画解析

Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def maxNumber(self, nums1, nums2, k):

        def max_stack(nums, k):
            stack = []
            remain = len(nums) - k
            for num in nums:
                while remain and stack and stack[-1] < num:
                    stack.pop()
                    remain -= 1
                stack.append(num)
            return stack[:k]

        def merge(A, B):
            res = []
            while A or B:
                bigger = A if A > B else B
                ans.append(bigger[0])
                bigger.pop(0)
            return res

        return max(merge(max_stack(nums1, i), max_stack(nums2, k-i)) for i in range(k+1) if i <= len(nums1) and k-i <= len(nums2))

参考：https://leetcode-cn.com/u/fe-lucifer/