跳至主要內容

942. 增减字符串匹配


942. 增减字符串匹配

🟢   🔖  贪心 数组 双指针 字符串  🔗 力扣open in new window LeetCodeopen in new window

题目

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 = 0right = nn 是字符串 s 的长度。结果数组 res 为空。
  2. 遍历字符串
    • 遇到字符 'I':将 left 的值加入数组,并将 left 自增。
    • 遇到字符 'D':将 right 的值加入数组,并将 right 自减。
  3. 处理最后一个数:由于字符串长度为 n,结果数组需要 n+1 个元素。最后一个数可以是 leftright(两者此时相等)。
  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+🟠🀄️open in new window 🔗open in new window