题目描述
思路解析动画文字版
记牢这一套:小数字排队入栈、遇 I 或到末尾就整段倒出。下面每一帧都在套它。
主例 IIIDIDDD · 总览：上方是 pattern 的 8 个字符,I 表示这一位要比后一位小、D 表示要比后一位大。中间竖格子就是栈,现在空的。做法是让还没用过的最小数字 1、2、3 一个个入栈,一旦当前位是 I 或者扫到末尾,就把栈里攒的数字全倒出来接到答案后面。
主例 IIIDIDDD · 第 0 步压入 1(遇 I)：把候选数字 1 压进栈,栈里是 [1]。当前第 0 位是 I,表示前面这段连续 D 到此结束,该清栈了。按后进先出把栈倒空、完成前面的下降段;倒出的最后一个、也是最小的那个数字,正好落在第 0 位;下一轮会拿更大的、还没用过的数字接在它右边,这一位就比后一位小,I 成立。
主例 IIIDIDDD · 弹出 1 接到答案：栈顶弹出 1,接到答案后面,num 现在是 1。这一段栈已经倒空,栈里剩 []。
主例 IIIDIDDD · 第 1 步压入 2(遇 I)：把候选数字 2 压进栈,栈里是 [2]。当前第 1 位是 I,表示前面这段连续 D 到此结束,该清栈了。按后进先出把栈倒空、完成前面的下降段;倒出的最后一个、也是最小的那个数字,正好落在第 1 位;下一轮会拿更大的、还没用过的数字接在它右边,这一位就比后一位小,I 成立。
主例 IIIDIDDD · 弹出 2 接到答案：栈顶弹出 2,接到答案后面,num 现在是 12。这一段栈已经倒空,栈里剩 []。
主例 IIIDIDDD · 第 2 步压入 3(遇 I)：把候选数字 3 压进栈,栈里是 [3]。当前第 2 位是 I,表示前面这段连续 D 到此结束,该清栈了。按后进先出把栈倒空、完成前面的下降段;倒出的最后一个、也是最小的那个数字,正好落在第 2 位;下一轮会拿更大的、还没用过的数字接在它右边,这一位就比后一位小,I 成立。
主例 IIIDIDDD · 弹出 3 接到答案：栈顶弹出 3,接到答案后面,num 现在是 123。这一段栈已经倒空,栈里剩 []。
主例 IIIDIDDD · 第 3 步压入 4(遇 D,先攒着)：把候选数字 4 压进栈,栈里是 [4]。当前第 3 位是 D,要求这一位比后一位大,那就先别急着倒,继续往栈里攒。攒得越多,等会儿倒出来的下降段就越长。
主例 IIIDIDDD · 第 4 步压入 5(遇 I)：把候选数字 5 压进栈,栈里是 [4,5]。当前第 4 位是 I,表示前面这段连续 D 到此结束,该清栈了。按后进先出把栈倒空、完成前面的下降段;倒出的最后一个、也是最小的那个数字,正好落在第 4 位;下一轮会拿更大的、还没用过的数字接在它右边,这一位就比后一位小,I 成立。
主例 IIIDIDDD · 弹出 5 接到答案：栈顶弹出 5,接到答案后面,num 现在是 1235。栈里还剩 [4],接着弹下一个,越靠栈底的数字越小、越晚出来,正好排成下降。
主例 IIIDIDDD · 弹出 4 接到答案：栈顶弹出 4,接到答案后面,num 现在是 12354。这一段栈已经倒空,栈里剩 []。
主例 IIIDIDDD · 第 5 步压入 6(遇 D,先攒着)：把候选数字 6 压进栈,栈里是 [6]。当前第 5 位是 D,要求这一位比后一位大,那就先别急着倒,继续往栈里攒。攒得越多,等会儿倒出来的下降段就越长。
主例 IIIDIDDD · 第 6 步压入 7(遇 D,先攒着)：把候选数字 7 压进栈,栈里是 [6,7]。当前第 6 位是 D,要求这一位比后一位大,那就先别急着倒,继续往栈里攒。攒得越多,等会儿倒出来的下降段就越长。
主例 IIIDIDDD · 第 7 步压入 8(遇 D,先攒着)：把候选数字 8 压进栈,栈里是 [6,7,8]。当前第 7 位是 D,要求这一位比后一位大,那就先别急着倒,继续往栈里攒。攒得越多,等会儿倒出来的下降段就越长。
主例 IIIDIDDD · 第 8 步压入 9(末尾)：把最后一个候选数字 9 压进栈,现在栈里自底向上是 [6,7,8,9]。pattern 已经走完,末尾这里必须把栈清空,才能凑够 9 位。
主例 IIIDIDDD · 弹出 9 接到答案：栈顶弹出 9,接到答案后面,num 现在是 123549。栈里还剩 [6,7,8],接着弹下一个,越靠栈底的数字越小、越晚出来,正好排成下降。
主例 IIIDIDDD · 弹出 8 接到答案：栈顶弹出 8,接到答案后面,num 现在是 1235498。栈里还剩 [6,7],接着弹下一个,越靠栈底的数字越小、越晚出来,正好排成下降。
主例 IIIDIDDD · 弹出 7 接到答案：栈顶弹出 7,接到答案后面,num 现在是 12354987。栈里还剩 [6],接着弹下一个,越靠栈底的数字越小、越晚出来,正好排成下降。
主例 IIIDIDDD · 弹出 6 接到答案：栈顶弹出 6,接到答案后面,num 现在是 123549876。这一段栈已经倒空,栈里剩 []。
主例 IIIDIDDD · 收束,答案 = 123549876：全部字符处理完、栈也倒空,最终 num = 123549876。每一步都用当时还没用过的最小数字,又靠栈把每一段 D 翻成倒序,凑出来的就是字典序最小的答案。
对照 DDD · 总览：上方是 pattern 的 3 个字符,I 表示这一位要比后一位小、D 表示要比后一位大。中间竖格子就是栈,现在空的。做法是让还没用过的最小数字 1、2、3 一个个入栈,一旦当前位是 I 或者扫到末尾,就把栈里攒的数字全倒出来接到答案后面。
对照 DDD · 第 0 步压入 1(遇 D,先攒着)：把候选数字 1 压进栈,栈里是 [1]。当前第 0 位是 D,要求这一位比后一位大,那就先别急着倒,继续往栈里攒。攒得越多,等会儿倒出来的下降段就越长。
对照 DDD · 第 1 步压入 2(遇 D,先攒着)：把候选数字 2 压进栈,栈里是 [1,2]。当前第 1 位是 D,要求这一位比后一位大,那就先别急着倒,继续往栈里攒。攒得越多,等会儿倒出来的下降段就越长。
对照 DDD · 第 2 步压入 3(遇 D,先攒着)：把候选数字 3 压进栈,栈里是 [1,2,3]。当前第 2 位是 D,要求这一位比后一位大,那就先别急着倒,继续往栈里攒。攒得越多,等会儿倒出来的下降段就越长。
对照 DDD · 第 3 步压入 4(末尾)：把最后一个候选数字 4 压进栈,现在栈里自底向上是 [1,2,3,4]。pattern 已经走完,末尾这里必须把栈清空,才能凑够 4 位。
对照 DDD · 整段倒出 [4,3,2,1]：把栈里 [1,2,3,4] 一次性倒光,后进先出,出来的顺序正好是 4、3、2、1,接到答案后面。num 现在是 4321,栈重新清空。
对照 DDD · 收束,答案 = 4321：全部字符处理完、栈也倒空,最终 num = 4321。每一步都用当时还没用过的最小数字,又靠栈把每一段 D 翻成倒序,凑出来的就是字典序最小的答案。
边界想清:单个 I 是 12、单个 D 是 21、全 I 就是 12345 这样的顺次升序。
面试重点:小数字入栈遇 I 或末尾倒出、逐位取最小保证字典序最小、贪心栈 O(n) 也可回溯。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def smallestNumber(self, pattern: str) -> str: def dfs(u): nonlocal ans if ans: return if u == len(pattern) + 1: ans = ''.join(t) return for i in range(1, 10): if not vis[i]: if u and pattern[u - 1] == 'I' and int(t[-1]) >= i: continue if u and pattern[u - 1] == 'D' and int(t[-1]) <= i: continue vis[i] = True t.append(str(i)) dfs(u + 1) vis[i] = False t.pop() vis = [False] * 10 t = [] ans = None dfs(0) return ans复杂度
- 时间：O(n)，这里的 O(n) 只说贪心栈:每个候选数字恰好入栈一次、出栈一次,pattern 每位只看一眼决定要不要清栈,总操作数随 n 线性增长。参考代码的回溯不是线性,最坏时每位都要从 1 到 9 试、失败再回退,只是靠本题 pattern 最长 8、数字最多 9 个的小范围才能通过,不能按 O(n) 理解
- 空间：O(n)，按峰值算。栈里最多同时攒着一整段连续 D 对应的数字,最坏是全是 D 时栈深接近 n 加 1;答案串本身也是 n 加 1 长。参考代码则是递归栈加长度 10 的 vis 表,深度到 n 加 1
易错点
面试追问把动画讲成自己的话
追问这题贪心栈的核心思路一句话是什么?
追问为什么这样贪心是对的,不会漏掉更小的解?
追问除了贪心栈还能怎么做,复杂度如何?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
被列覆盖的最多行数
LeetCode 2397 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题