2375-根据模式串构造最小数字

给你下标从 0 开始、长度为 n 的字符串 pattern ，它包含两种字符，'I' 表示 上升 ，'D' 表示
下降 。

你需要构造一个下标从 0 开始长度为 n + 1 的字符串，且它要满足以下条件：

• 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' 使用次数超过 1 次。

示例 2：

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

提示：

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

本题 视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

---

贪心策略：

把 pattern 按照 III}\cdots \texttt{IDDD}\cdots \texttt{D 分组，每组前一段是 I，后一段是 D。

遍历每一段，设当前段的长度为 x，我们应该把剩余最小的 x 个数字填到该段上（如果是第一段则填最小的 x+1 个数字），从而保证字典序最小。

举例说明，假如第一段为 IIIDDD，构造方案如下：

• 前 2 个 I 视作长度为 3 的上升段；
• 剩余的 I 和 D 视作长度为 4 的下降段；
• 最小的 3 个数给上升段，然后剩余最小的 4 个数给下降段；
• 构造结果为 1237654。

按照该方案分组模拟即可。

视频讲解 中介绍了另外一种更优雅的做法。

[sol1-Python3]

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        i, cur, n = 0, 1, len(pattern)
        ans = [''] * (n + 1)
        while i < n:
            if i and pattern[i] == 'I':
                i += 1
            while i < n and pattern[i] == 'I':
                ans[i] = digits[cur]
                cur += 1
                i += 1
            i0 = i
            while i < n and pattern[i] == 'D':
                i += 1
            for j in range(i, i0 - 1, -1):
                ans[j] = digits[cur]
                cur += 1
        return ''.join(ans)

[sol1-Java]

class Solution {
    public String smallestNumber(String pattern) {
        int i = 0, n = pattern.length();
        var cur = '1';
        var ans = new char[n + 1];
        while (i < n) {
            if (i > 0 && pattern.charAt(i) == 'I') ++i;
            for (; i < n && pattern.charAt(i) == 'I'; ++i) ans[i] = cur++;
            var i0 = i;
            while (i < n && pattern.charAt(i) == 'D') ++i;
            for (var j = i; j >= i0; --j) ans[j] = cur++;
        }
        return new String(ans);
    }
}

[sol1-C++]

class Solution {
public:
    string smallestNumber(string pattern) {
        int i = 0, n = pattern.length();
        char cur = '1';
        string ans(n + 1, 0);
        while (i < n) {
            if (i && pattern[i] == 'I') ++i;
            for (; i < n && pattern[i] == 'I'; ++i) ans[i] = cur++;
            int i0 = i;
            while (i < n && pattern[i] == 'D') ++i;
            for (int j = i; j >= i0; --j) ans[j] = cur++;
        }
        return ans;
    }
};

[sol1-Go]

func smallestNumber(pattern string) string {
	n := len(pattern)
	ans := make([]byte, n+1)
	for i, cur := 0, byte('1'); i < n; {
		if i > 0 && pattern[i] == 'I' {
			i++
		}
		for ; i < n && pattern[i] == 'I'; i++ {
			ans[i] = cur
			cur++
		}
		i0 := i
		for ; i < n && pattern[i] == 'D'; i++ {
		}
		for j := i; j >= i0; j-- {
			ans[j] = cur
			cur++
		}
	}
	return string(ans)
}