2023-04-11：给你下标从 0 开始、长度为 n 的字符串 pattern ，
它包含两种字符，'I' 表示 上升 ，'D' 表示 下降 。
你需要构造一个下标从 0 开始长度为 n 1 的字符串，且它要满足以下条件：
num 包含数字 '1' 到 '9' ，其中每个数字 至多 使用一次。
如果 patterni == 'I' ，那么 numi < numi 1 。
如果 patterni == 'D' ，那么 numi > numi 1 。
请你返回满足上述条件字典序 最小 的字符串 num。
输入：pattern = "IIIDIDDD"，
输出："123549876"。
答案2023-04-11：
解题思路
这是一道比较有趣的贪心题目。我们可以根据给定的 pattern 字符串来决定数字串中相邻两个数的关系。
步骤1：定义 next 函数
首先，我们需要定义一个函数 next(status, num)，用来查找在状态 status 中没有使用过的最小数字（大于 num）。该函数通过遍历数字 1 到 9，判断哪些数字在 status 中未被使用，且大于 num，然后返回其中最小的数字。
代码语言：rust复制fn next(status: usize, num: u8) -> Option<u8> {
for i in (num 1)..=9 {
if (status & (1 << i)) == 0 {
return Some(i as u8);
}
}
None
}步骤2：定义 create 函数
接着，我们需要定义另一个函数 create(pattern, index, status, number)，用来递归生成数字串，并判断是否符合要求。在递归过程中，我们需要判断当前位应该填入哪个数字，并根据数字的大小关系更新 status、number 和 index 的值。如果生成的数字串不符合要求，则需要回溯并重新选择数字。
代码语言：rust复制fn create(pattern: &[char], index: usize, status: &mut usize, number: &mut u32) -> bool {
if index == pattern.len() 1 {
return true;
}
let mut cur = 0;
while let Some(next_cur) = next(*status, cur) {
cur = next_cur;
// cur == 0 , 当前位，1 X
// cur == 1 , 当前位，2 X
// cur == 2, 当前位，4
// pattern I D >
// 0 1 2 3
// ? ? ? ?
// D
// 0 1
// 5 ?
if index == 0
|| (pattern[index - 1] == 'I' && *number % 10 < cur as u32)
|| (pattern[index - 1] == 'D' && *number % 10 > cur as u32)
{
*status |= 1 << cur;
*number = *number * 10 cur as u32;
if create(pattern, index 1, status, number) {
return true;
}
*number /= 10;
*status &= !(1 << cur);
}
}
false
}步骤3：定义 smallest_number 函数
最后，我们需要定义 smallest_number 函数，调用 create 函数来生成数字串，并将其转化为字符串类型返回。
代码语言：rust复制fn smallest_number(pattern: &str) -> String {
let chars = pattern.chars().collect::<Vec<_>>();
let mut status = 0usize;
let mut number = 0;
create(&chars, 0, &mut status, &mut number);
number.to_string()
}时间复杂度
对于这个解法，最坏情况下需要枚举所有可能的数字串，因此时间复杂度为 O(n * 9!)，其中 n 是 pattern 字符串的长度。在实际测试中，由于存在大量剪枝操作，实际运行时间要比这个上界要小得多。
空间复杂度
主要的存储空间是用来记录数字是否被使用过的 status 变量和已经生成的数字串 number 变量，以及递归调用栈所占用的空间。其中，status 和 number 变量的大小均为常数级别，因此空间复杂度为 O(1)。递归调用栈的深度最多为 n 1，因此空间复杂度为 O(n)。
rust完整代码如下：
代码语言：rust复制fn smallest_number(pattern: &str) -> String {
let chars = pattern.chars().collect::<Vec<_>>();
let mut status = 0usize;
let mut number = 0;
create(&chars, 0, &mut status, &mut number);
number.to_string()
}
/// 返回 i... 所有数字都决定了，并且不破坏pattern，
/// 并且1~9每个数字最多用一次能出来的最小值是啥，返回
fn create(pattern: &[char], index: usize, status: &mut usize, number: &mut u32) -> bool {
if index == pattern.len() 1 {
return true;
}
let mut cur = 0;
while let Some(next_cur) = next(*status, cur) {
cur = next_cur;
// cur == 0 , 当前位，1 X
// cur == 1 , 当前位，2 X
// cur == 2, 当前位，4
// pattern I D >
// 0 1 2 3
// ? ? ? ?
// D
// 0 1
// 5 ?
if index == 0
|| (pattern[index - 1] == 'I' && *number % 10 < cur as u32)
|| (pattern[index - 1] == 'D' && *number % 10 > cur as u32)
{
*status |= 1 << cur;
*number = *number * 10 cur as u32;
if create(pattern, index 1, status, number) {
return true;
}
*number /= 10;
*status &= !(1 << cur);
}
}
false
}
/// 返回没有使用，且 > num, 最小的数字
fn next(status: usize, num: u8) -> Option<u8> {
for i in (num 1)..=9 {
if (status & (1 << i)) == 0 {
return Some(i as u8);
}
}
None
}
fn main() {
let pattern = "IIIDIDDD";
let result = smallest_number(pattern);
println!("{}", result); // 输出：123549876
}
