942. 增减字符串匹配

🟢   🔖  贪心 数组 双指针 字符串  🔗 力扣 LeetCode

题目

A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where:

• s[i] == 'I' if perm[i] < perm[i + 1], and
• s[i] == 'D' if perm[i] > perm[i + 1].

Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.

Example 1:

Input: s = "IDID"

Output: [0,4,1,3,2]

Example 2:

Input: s = "III"

Output: [0,1,2,3]

Example 3:

Input: s = "DDI"

Output: [3,2,0,1]

Constraints:

• 1 <= s.length <= 10^5
• s[i] is either 'I' or 'D'.

题目大意

由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:

• 如果 perm[i] < perm[i + 1] ，那么 s[i] == 'I'
• 如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D'

给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列 perm，则返回其中 任何一个 。

示例 1：

输入： s = "IDID"

输出：[0,4,1,3,2]

示例 2：

输入： s = "III"

输出：[0,1,2,3]

示例 3：

输入： s = "DDI"

输出：[3,2,0,1]

提示：

• 1 <= s.length <= 10^5
• s 只包含字符 "I" 或 "D"

解题思路

可以使用双指针的方法，分别从数组的最小值 left 和最大值 right 开始分配：

1. 初始化：令 left = 0 和 right = n，n 是字符串 s 的长度。结果数组 res 为空。
2. 遍历字符串：
   • 遇到字符 'I'：将 left 的值加入数组，并将 left 自增。
   • 遇到字符 'D'：将 right 的值加入数组，并将 right 自减。
3. 处理最后一个数：由于字符串长度为 n，结果数组需要 n+1 个元素。最后一个数可以是 left 或 right（两者此时相等）。
4. 返回结果数组 res。

复杂度分析

• 时间复杂度: O(n)，需要遍历字符串 s 一次。
• 空间复杂度: O(n)，用于存储结果数组 res。

代码

/**
 * @param {string} s
 * @return {number[]}
 */
var diStringMatch = function (s) {
	const n = s.length;
	let res = [];
	let left = 0,
		right = n;
	for (let char of s) {
		if (char === 'I') {
			res.push(left++);
		} else {
			res.push(right--);
		}
	}
	res.push(left); // 此时 left 和 right 应该相等
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
2375	根据模式串构造最小数字	[✓]	栈 贪心 字符串 1+	🟠	🀄️ 🔗