Medium

题目描述

给你一个长度为 n 、下标从 0 开始的字符串 pattern ，它包含字符 'I' 表示递增和 'D' 表示递减。

请你创建一个下标从 0 开始、长度为 n + 1 的字符串 num ，并满足以下条件：

  • num 只包含数字 '1' 到 '9' ，其中每个数字 最多 使用一次。
  • 如果 pattern[i] == 'I' ，那么 num[i] < num[i + 1]。
  • 如果 pattern[i] == 'D' ，那么 num[i] > num[i + 1]。

请你返回满足上述条件 字典序最小 的字符串 num。

示例 1：

输入：pattern = "IIIDIDDD"
输出："123549876"
解释：
下标 0、1、2 和 4 处，我们需要 num[i] < num[i+1] 。
下标 3、5、6 和 7 处，我们需要 num[i] > num[i+1] 。
一些可能的 num 值为 "245639871"、"135749862" 和 "123849765" 。
可以证明，"123549876" 是满足条件的最小值。
注意，"123414321" 不是可行的，因为数字 '1' 使用了超过一次。

示例 2：

输入：pattern = "DDD"
输出："4321"
解释：
一些可能的 num 值为 "9876"、"7321" 和 "8742" 。
可以证明，"4321" 是满足条件的最小值。

约束：

  • 1 <= pattern.length <= 8
  • pattern 只包含字符 'I' 和 'D' 。

解题思路

这道题要求构造一个满足模式的字典序最小的数字字符串。有多种解法：

方法一：回溯法 使用回溯枚举所有可能的数字组合，找到第一个满足条件的就是答案。由于约束较小（最多9位），时间复杂度可接受。

方法二：贪心 + 栈 观察规律：遇到连续的’D’时，我们需要让这段区间内的数字递减。可以使用栈来处理：

  • 遇到’I’时，弹出栈中所有元素并分配数字
  • 遇到’D’时，将位置压入栈
  • 最后处理剩余的栈元素

方法三：模拟构造（推荐） 核心思想是找到每个连续’D’段的范围，在该范围内逆序填充数字。具体步骤：

  1. 从小到大依次分配数字1,2,3…
  2. 遇到’D’时记录连续’D’的起始位置
  3. 连续’D’结束时，将这段区间的数字逆序

这种方法最直观且高效，时间复杂度O(n)，空间复杂度O(1)。

代码实现

class Solution {
public:
    string smallestNumber(string pattern) {
        int n = pattern.size();
        string result(n + 1, '0');
        
        // 先按顺序填充数字
        for (int i = 0; i <= n; i++) {
            result[i] = '1' + i;
        }
        
        // 处理'D'段，将连续的'D'段逆序
        int i = 0;
        while (i <= n) {
            int j = i;
            // 找到连续'D'的结束位置
            while (j < n && pattern[j] == 'D') {
                j++;
            }
            // 如果找到了'D'段，将[i, j]范围逆序
            if (j > i) {
                reverse(result.begin() + i, result.begin() + j + 1);
            }
            i = j + 1;
        }
        
        return result;
    }
};

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        n = len(pattern)
        # 初始化结果数组，先按顺序填充
        result = [str(i + 1) for i in range(n + 1)]
        
        # 处理'D'段
        i = 0
        while i <= n:
            j = i
            # 找到连续'D'的结束位置
            while j < n and pattern[j] == 'D':
                j += 1
            # 如果找到了'D'段，将[i, j]范围逆序
            if j > i:
                result[i:j+1] = result[i:j+1][::-1]
            i = j + 1
        
        return ''.join(result)

public class Solution {
    public string SmallestNumber(string pattern) {
        int n = pattern.Length;
        char[] result = new char[n + 1];
        
        // 先按顺序填充数字
        for (int i = 0; i <= n; i++) {
            result[i] = (char)('1' + i);
        }
        
        // 处理'D'段
        int i = 0;
        while (i <= n) {
            int j = i;
            // 找到连续'D'的结束位置
            while (j < n && pattern[j] == 'D') {
                j++;
            }
            // 如果找到了'D'段，将[i, j]范围逆序
            if (j > i) {
                Array.Reverse(result, i, j - i + 1);
            }
            i = j + 1;
        }
        
        return new string(result);
    }
}

var smallestNumber = function(pattern) {
    const n = pattern.length;
    // 先按顺序填充数字
    let result = Array.from({length: n + 1}, (_, i) => String(i + 1));
    
    // 处理'D'段
    let i = 0;
    while (i <= n) {
        let j = i;
        // 找到连续'D'的结束位置
        while (j < n && pattern[j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n) - 遍历模式字符串一次，逆序操作的总时间复杂度也是O(n)
空间复杂度O(1) - 除了结果数组外，只使用常数额外空间

相关题目