0942. DI String Match¶
题目信息¶
- 题号:
0942
- 难度:
Easy
- 主题:
构造、排列、相邻大小关系
- 原题:
- 重点:
长度为
n的模式需要返回0至n的一个排列;I与D分别约束相邻元素严格递增或严格递减,任意合法排列均可
题目重述¶
给定只包含字符 I 和 D 的字符串 s,令其长度为 n。构造数组 perm,使它恰好包含整数 0, 1, ..., n 各一次。
对于每个下标 i,若 s[i] == 'I',必须满足 perm[i] < perm[i + 1];若 s[i] == 'D',必须满足 perm[i] > perm[i + 1]。返回任意一个满足全部关系的排列。
1 <= s.length <= 10^5。
自建示例¶
交替下降、上升、下降:
输入:s = "DID"
输出:[3,0,2,1]
解释:3 > 0、0 < 2、2 > 1,且数组恰好包含 0、1、2、3。其他合法排列也可以返回。
模式长度达到最小值:
输入:s = "I"
输出:[0,1]
解释:排列只需包含 0 和 1,且满足 0 < 1;这是唯一合法结果。