LeetCode 2375中等回溯 · 枚举
根据模式串构造最小数字 图解题解
这道题到底在问什么
给定长度为 n 的字符串 pattern,只含 I 和 D。要构造长度为 n 加 1 的数字串 num,只用数字 1 到 9 且每个至多一次。若 pattern[i] 是 I 则 num[i] < num[i+1];若是 D 则 num[i] > num[i+1]。返回满足条件且字典序最小的 num。
- 输入
- pattern = "IIIDIDDD"
- 输出
- "123549876"
- 输入
- pattern = "DDD"
- 输出
- "4321"
最优解：一步一步想明白
- 3记牢这一套:小数字排队入栈、遇 I 或到末尾就整段倒出。下面每一帧都在套它。
- 4上方是 pattern 的 8 个字符,I 表示这一位要比后一位小、D 表示要比后一位大。中间竖格子就是栈,现在空的。做法是让还没用过的最小数字 1、2、3 一个个入栈,一旦当前位是 I 或者扫到末尾,就把栈里攒的数字全倒出来接到答案后面。
- 5把候选数字 1 压进栈,栈里是 [1]。当前第 0 位是 I,表示前面这段连续 D 到此结束,该清栈了。按后进先出把栈倒空、完成前面的下降段;倒出的最后一个、也是最小的那个数字,正好落在第 0 位;下一轮会拿更大的、还没用过的数字接在它右边,这一位就比后一位小,I 成立。
- 6栈顶弹出 1,接到答案后面,num 现在是 1。这一段栈已经倒空,栈里剩 []。
- 7把候选数字 2 压进栈,栈里是 [2]。当前第 1 位是 I,表示前面这段连续 D 到此结束,该清栈了。按后进先出把栈倒空、完成前面的下降段;倒出的最后一个、也是最小的那个数字,正好落在第 1 位;下一轮会拿更大的、还没用过的数字接在它右边,这一位就比后一位小,I 成立。
- 8栈顶弹出 2,接到答案后面,num 现在是 12。这一段栈已经倒空,栈里剩 []。
- 9把候选数字 3 压进栈,栈里是 [3]。当前第 2 位是 I,表示前面这段连续 D 到此结束,该清栈了。按后进先出把栈倒空、完成前面的下降段;倒出的最后一个、也是最小的那个数字,正好落在第 2 位;下一轮会拿更大的、还没用过的数字接在它右边,这一位就比后一位小,I 成立。
- 10栈顶弹出 3,接到答案后面,num 现在是 123。这一段栈已经倒空,栈里剩 []。
- 11把候选数字 4 压进栈,栈里是 [4]。当前第 3 位是 D,要求这一位比后一位大,那就先别急着倒,继续往栈里攒。攒得越多,等会儿倒出来的下降段就越长。
- 12把候选数字 5 压进栈,栈里是 [4,5]。当前第 4 位是 I,表示前面这段连续 D 到此结束,该清栈了。按后进先出把栈倒空、完成前面的下降段;倒出的最后一个、也是最小的那个数字,正好落在第 4 位;下一轮会拿更大的、还没用过的数字接在它右边,这一位就比后一位小,I 成立。
- 13栈顶弹出 5,接到答案后面,num 现在是 1235。栈里还剩 [4],接着弹下一个,越靠栈底的数字越小、越晚出来,正好排成下降。
- 14栈顶弹出 4,接到答案后面,num 现在是 12354。这一段栈已经倒空,栈里剩 []。
- 15把候选数字 6 压进栈,栈里是 [6]。当前第 5 位是 D,要求这一位比后一位大,那就先别急着倒,继续往栈里攒。攒得越多,等会儿倒出来的下降段就越长。
- 16把候选数字 7 压进栈,栈里是 [6,7]。当前第 6 位是 D,要求这一位比后一位大,那就先别急着倒,继续往栈里攒。攒得越多,等会儿倒出来的下降段就越长。
- 17把候选数字 8 压进栈,栈里是 [6,7,8]。当前第 7 位是 D,要求这一位比后一位大,那就先别急着倒,继续往栈里攒。攒得越多,等会儿倒出来的下降段就越长。
- 18把最后一个候选数字 9 压进栈,现在栈里自底向上是 [6,7,8,9]。pattern 已经走完,末尾这里必须把栈清空,才能凑够 9 位。
- 19栈顶弹出 9,接到答案后面,num 现在是 123549。栈里还剩 [6,7,8],接着弹下一个,越靠栈底的数字越小、越晚出来,正好排成下降。
- 20栈顶弹出 8,接到答案后面,num 现在是 1235498。栈里还剩 [6,7],接着弹下一个,越靠栈底的数字越小、越晚出来,正好排成下降。
- 21栈顶弹出 7,接到答案后面,num 现在是 12354987。栈里还剩 [6],接着弹下一个,越靠栈底的数字越小、越晚出来,正好排成下降。
- 22栈顶弹出 6,接到答案后面,num 现在是 123549876。这一段栈已经倒空,栈里剩 []。
- 23全部字符处理完、栈也倒空,最终 num = 123549876。每一步都用当时还没用过的最小数字,又靠栈把每一段 D 翻成倒序,凑出来的就是字典序最小的答案。
- 24上方是 pattern 的 3 个字符,I 表示这一位要比后一位小、D 表示要比后一位大。中间竖格子就是栈,现在空的。做法是让还没用过的最小数字 1、2、3 一个个入栈,一旦当前位是 I 或者扫到末尾,就把栈里攒的数字全倒出来接到答案后面。
- 25把候选数字 1 压进栈,栈里是 [1]。当前第 0 位是 D,要求这一位比后一位大,那就先别急着倒,继续往栈里攒。攒得越多,等会儿倒出来的下降段就越长。
- 26把候选数字 2 压进栈,栈里是 [1,2]。当前第 1 位是 D,要求这一位比后一位大,那就先别急着倒,继续往栈里攒。攒得越多,等会儿倒出来的下降段就越长。
- 27把候选数字 3 压进栈,栈里是 [1,2,3]。当前第 2 位是 D,要求这一位比后一位大,那就先别急着倒,继续往栈里攒。攒得越多,等会儿倒出来的下降段就越长。
- 28把最后一个候选数字 4 压进栈,现在栈里自底向上是 [1,2,3,4]。pattern 已经走完,末尾这里必须把栈清空,才能凑够 4 位。
- 29把栈里 [1,2,3,4] 一次性倒光,后进先出,出来的顺序正好是 4、3、2、1,接到答案后面。num 现在是 4321,栈重新清空。
- 30全部字符处理完、栈也倒空,最终 num = 4321。每一步都用当时还没用过的最小数字,又靠栈把每一段 D 翻成倒序,凑出来的就是字典序最小的答案。
⚠️ 容易写错的地方
✗ 错：遇到 D 就立刻把栈倒出来
✓ 对：遇 D 先攒着,只有遇 I 或到末尾才清栈
D 要求这一位比后一位大,得先把后面更小的数字凑齐、靠栈翻成倒序才对;过早倒出会打乱下降段
✗ 错：每段随便挑数字凑升降关系
✓ 对：永远拿当前还没用过的最小数字入栈
只满足升降还不够,题目要字典序最小,高位越小越好,所以候选必须从最小的数字开始用
✗ 错：把栈从底往上顺着接到答案
✓ 对：要后进先出,从栈顶往下弹
栈顶是这一段里最大的数字,先出来占前一位,后面接更小的,才形成下降;顺着接会变成升序,方向反了
✗ 错：忘了末尾也要清一次栈
✓ 对：扫到 pattern 末尾必须把栈全部倒空
最后一段 D 攒下的数字还留在栈里,不清空答案就短一截、位数不够 n 加 1
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
string ans = "";
string pattern;
vector<bool> vis;
string t = "";
string smallestNumber(string pattern) {
this->pattern = pattern;
vis.assign(10, false);
dfs(0);
return ans;
}
void dfs(int u) {
if (ans != "") return;
if (u == pattern.size() + 1) {
ans = t;
return;
}
for (int i = 1; i < 10; ++i) {
if (!vis[i]) {
if (u && pattern[u - 1] == 'I' && t.back() - '0' >= i) continue;
if (u && pattern[u - 1] == 'D' && t.back() - '0' <= i) continue;
vis[i] = true;
t += to_string(i);
dfs(u + 1);
t.pop_back();
vis[i] = false;
}
}
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
private boolean[] vis = new boolean[10];
private StringBuilder t = new StringBuilder();
private String p;
private String ans;
public String smallestNumber(String pattern) {
p = pattern;
dfs(0);
return ans;
}
private void dfs(int u) {
if (ans != null) {
return;
}
if (u == p.length() + 1) {
ans = t.toString();
return;
}
for (int i = 1; i < 10; ++i) {
if (!vis[i]) {
if (u > 0 && p.charAt(u - 1) == 'I' && t.charAt(u - 1) - '0' >= i) {
continue;
}
if (u > 0 && p.charAt(u - 1) == 'D' && t.charAt(u - 1) - '0' <= i) {
continue;
}
vis[i] = true;
t.append(i);
dfs(u + 1);
t.deleteCharAt(t.length() - 1);
vis[i] = false;
}
}
}
}复杂度
时间
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
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 根据模式串构造最小数字 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题贪心栈的核心思路一句话是什么?+
让还没用过的最小数字 1、2、3 依次入栈,遇到 I 或扫到末尾就把栈整段倒出接到答案后面。升序段直接顺次给小数字,下降段靠栈后进先出翻成倒序,又因为始终用最小数字,结果就是字典序最小。
为什么这样贪心是对的,不会漏掉更小的解?+
字典序由高位决定,高位越小越好。每一段在必须满足升降关系的前提下,我们都只动用「当前能用的最小的一段连续数字」,没有把大数字提前浪费到高位。栈保证一段 D 被正确翻转,I 处及时清栈保证升序。逐位都取到了可行的最小值,自然是全局最小。
除了贪心栈还能怎么做,复杂度如何?+
可以像参考代码那样回溯:每一位从 1 到 9 由小到大试,满足升降且没用过就往下递归,第一个凑满全长的解就是答案。它靠从小到大试保证字典序最小。贪心栈是 O(n) 时间 O(n) 空间;回溯最坏要反复试错回退、并不是线性,只是本题 pattern 最长 8、数字最多 9 个,范围小才跑得动。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 根据模式串构造最小数字 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。