LeeCode 942 增减字符串匹配

LeeCode 942

题目描述：

由范围 [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，则返回其中任何一个。

标签： 贪心选择、排序

建立模型

解法一

直观看这个题想到的就是两层排序的思路，遍历比较相邻位置的大小关系是否匹配字符串s，如果匹配则继续比较下一对；如果不匹配，则交换相邻两个数的位置，并向前比较和交换直到匹配或者越界。这种解法虽然思路非常清晰，但时间复杂度过高，效率较低。

时间复杂度：最坏情况可达\(O(N^2)\)

解法二

贪心选择的思路，如果当前字母s[i] == 'I', 则 res[i] = low 取可使用的最小值；如果当前字母s[i] == 'D', 则 res[i] = high 取可使用的最大值

时间复杂度：O(N)

编码实现

# 解法一编码实现

def diStringMatch(s: str) -> List[int]:

    res = [i for i in range(len(s) + 1)]

    left, right = 0, 1

    while right < len(res):

        i, j = left, right

        while i >=0 and ((s[i] == 'I' and res[i] > res[j]) or (s[i] == 'D' and res[i] < res[j])):

            res[i], res[j] = res[j], res[i]

            i -= 1

            j -= 1

        left += 1

        right += 1

    return res

# 解法二编码实现

def diStringMatch(s: str) -> List[int]:

    low, high = 0, len(s)

    res = [0 for i in range(len(s) + 1)]

    for i, c in enumerate(s):

        if c == 'I':

            res[i] = low

            low -= 1

        else:

            res[i] = high

            high -= 1

    res[len(s)] = low    # 移动到最后一个元素时 low = high

    return res

LeeCode 942 增减字符串匹配的相关教程结束。