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

🟠   🔖  栈 贪心 字符串 回溯  🔗 力扣 LeetCode

题目

You are given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing.

A 0-indexed string num of length n + 1 is created using the following conditions:

• num consists of the digits '1' to '9', where each digit is used at most once.
• If pattern[i] == 'I', then num[i] < num[i + 1].
• If pattern[i] == 'D', then num[i] > num[i + 1].

Return _the lexicographicallysmallest possible string _num that meets the conditions.

Example 1:

Input: pattern = "IIIDIDDD"

Output: "123549876"

Explanation: At indices 0, 1, 2, and 4 we must have that num[i] < num[i+1].

At indices 3, 5, 6, and 7 we must have that num[i] > num[i+1].

Some possible values of num are "245639871", "135749862", and "123849765".

It can be proven that "123549876" is the smallest possible num that meets the conditions.

Note that "123414321" is not possible because the digit '1' is used more than once.

Example 2:

Input: pattern = "DDD"

Output: "4321"

Explanation:

Some possible values of num are "9876", "7321", and "8742".

It can be proven that "4321" is the smallest possible num that meets the conditions.

Constraints:

• 1 <= pattern.length <= 8
• pattern consists of only the letters 'I' and 'D'.

题目大意

给你下标从 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 仅包含 I 和 D，并且 pattern 长度为 n，因此答案由 n+1 个不同的数字（1 到 n+1）组成。可以使用 贪心策略 + 单调栈：尽可能使左侧数字小，以确保整体的最小性。

1. 遍历 pattern 的索引 i，将 i+1 压入栈（因为最终结果包含 n+1 个数）。

2. 如果 pattern[i] == 'I' 或 i == n（遍历结束），依次弹出栈中的所有元素，加入 res 中。

3. 最后，将 res 数组转换成字符串返回。

复杂度分析

• 时间复杂度：O(n)，每个元素最多入栈和出栈一次。
• 空间复杂度：O(n)，使用 stack 额外存储 n+1 个元素。

代码

/**
 * @param {string} pattern
 * @return {string}
 */
var smallestNumber = function (pattern) {
	const n = pattern.length;
	let res = [];
	let stack = [];
	for (let i = 0; i <= n; i++) {
		stack.push(i + 1);
		if (pattern[i] == 'I' || i == n) {
			while (stack.length) {
				res.push(stack.pop());
			}
		}
	}
	return res.join('');
};

相关题目

题号	标题	题解	标签	难度	力扣
942	增减字符串匹配	[✓]	贪心 数组 双指针 1+	🟢	🀄️ 🔗