0%

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

其中 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。

动画解析

单调栈解字典序最小问题2

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. 拼接最大数

题目描述

给定长度分别为 mn 的两个数组,其元素由 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() 方法来合并,两个单调栈

动画解析

单调栈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/