0942. DI String Match

题目信息

题号:

0942

难度:

Easy

主题:

构造、排列、相邻大小关系

原题:

LeetCode 0942

重点:

长度为 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;这是唯一合法结果。