由范围 [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]
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/di-string-match
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
第一反应的做法是，连续的D意味着这一串数是倒序，而连续的I意味着这一串数是正序。因此只需要翻转为连续D的数即可
class Solution:
def diStringMatch(self, s: str) -> List[int]:
# solution 1
def reverse(st, ed):
nonlocal perm, ans
for i in range(st, ed+1):
perm[i] = ans[st+ed-i]
n = len(s)
perm = [i for i in range(n+1)]
ans = [i for i in range(n+1)]
start = end = 0
for i in range(n):
if s[i] == "D":
end += 1
if s[i] == "I":
reverse(start, end)
start = end = i+1
reverse(start, end)
return perm
时间复杂度是
O
(
N
2
)
O(N^2)
O(N2)，空间复杂度是
O
(
N
)
O(N)
O(N)。
所以这其实是一种不好的做法，当然 通过对 reverse 优化,空间复杂度是可以降到
O
(
1
）
O(1）
O(1）的，但是时间依然复杂，我们重新构思一下，不是重构序列，而是创建序列呢？
贪心算法：
如果是D就添加当前最大数，I就添加当前最小数。
class Solution:
def diStringMatch(self, s: str) -> List[int]:
st = 0
ed = n = len(s)
perm = [0] * (n + 1)
for i, ch in enumerate(s):
if ch == 'I':
perm[i] = st
st += 1
else:
perm[i] = ed
ed -= 1
perm[n] = ed
return perm
