【leetcode】942. DI String Match

题目如下：

Given a string S that only contains "I" (increase) or "D" (decrease), let N = S.length.

Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:

If S[i] == "I", then A[i] < A[i+1]

If S[i] == "D", then A[i] > A[i+1]

Example 1:
Input: "IDID"

Output: [0,4,1,3,2]
Example 2:
Input: "III"

Output: [0,1,2,3]
Example 3:
Input: "DDI"

Output: [3,2,0,1] 
Note:

1 <= S.length <= 10000

S only contains characters "I" or "D".

解题思路：题目很简单，可以考虑贪心算法。本题有这么一个前提，I的位置一定可以放当前能放的元素中最小的那个，而D的位置一定能放当前能放的元素中最大的那个。所以遍历S，如果是I，放入当前的最小值，同时最小值加一；如果是D，放入当前的最大值，同时最大值减一。

代码如下：

class Solution(object):

    def diStringMatch(self, S):

        """

        :type S: str

        :rtype: List[int]

        """

        low = 0

        high = len(S)

        res = []

        for i in S:

            if i == 'I':

                res.append(low)

                low += 1

            else:

                res.append(high)

                high -= 1

        res.append(low)

        return res

巴特西

【leetcode】942. DI String Match

最新文章

热门文章