942. 增减字符串匹配
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'
ifperm[i] < perm[i + 1]
, ands[i] == 'D'
ifperm[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
开始分配:
- 初始化:令
left = 0
和right = n
,n
是字符串s
的长度。结果数组res
为空。 - 遍历字符串:
- 遇到字符
'I'
:将left
的值加入数组,并将left
自增。 - 遇到字符
'D'
:将right
的值加入数组,并将right
自减。
- 遇到字符
- 处理最后一个数:由于字符串长度为
n
,结果数组需要n+1
个元素。最后一个数可以是left
或right
(两者此时相等)。 - 返回结果数组
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+ | 🟠 | 🀄️ 🔗 |