题目

难度：★☆☆☆☆
类型：数组

给定只含 "I"（增大）或 "D"（减小）的字符串 S ，令 N = S.length。

返回 [0, 1, ..., N] 的任意排列 A 使得对于所有 i = 0, ..., N-1，都有：

如果 S[i] == "I"，那么 A[i] < A[i+1]
如果 S[i] == "D"，那么 A[i] > A[i+1]

提示
1 <= S.length <= 1000
S 只包含字符 "I" 或 "D"。

示例

示例 1
输出："IDID"
输出：[0,4,1,3,2]

示例 2
输出："III"
输出：[0,1,2,3]

示例 3
输出："DDI"
输出：[3,2,0,1]

解答

为了把[0, ......, N]中的N+1个数都使用到，我们首先构建数组nums = [0, 1, 2, ......, N]；

每当遇到上升趋势时，我们弹出数组中的最小值，放在结果列表res中，这样可以确保下一个数比当前的数大；

每当遇到下降趋势时，我们弹出数组中的最大值，放在结果列表res中，这样可以确保下一个数比当前的数小；

最后，记得把nums中剩余的最后一个数取出来放进结果列表末尾。

class Solution:
    def diStringMatch(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        nums = list(range(len(S)+1))
        A = []
        for c in S:
            if c == 'I':
                A.append(nums.pop(0))
            elif c == 'D':
                A.append(nums.pop())
        A.append(nums.pop())
        return A

如有疑问或建议，欢迎评论区留言~