题目

给定只含 “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]

来源：https://leetcode-cn.com/problems/di-string-match

解题思路

官方提供的题解，维护可用的最大和最小 high，low 两个变量，每次需要递增时放入high，并使 high–；需要递减时放入low，并使low–；当S遍历结束后，追加最后剩下数。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def diStringMatch(self, S):
        lo, hi = 0, len(S)
        ans = []
        for x in S:
            if x == 'I':
                ans.append(lo)
                lo += 1
            else:
                ans.append(hi)
                hi -= 1
        return ans + [lo]

而下面要介绍的，和这个思路类似，但不同于维护相互靠近的两个变量，它维护的是向外远离的两个变量，即比当前数组内元素 刚好大/小一点 的 nextSmaller 和 nextBiger 变量。

另外，因为数组首元素放入0，数组可能放入负数，因此最后需要额外将所有元素向（0，N）范围偏移。代码如下：

tip: 因为放入数的取值范围依赖 S 的长度 N，因此无论官方题解的内缩还是第二种思路的外延，差值都是1，所以数组的所有元素差值正好为 N，不需要考虑重复数或超出(0，N)范围的情况

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def diStringMatch(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        a = [0]
        nextSmaller,nextBiger = -1,1
        for s in S:
            if(s =='I'):
                a.append(nextBiger)
                nextBiger+=1
            else:
                a.append(nextSmaller) 
                nextSmaller -= 1
        
        # minNum = 0 - min(a) 感谢 @瞌睡 指出 使用下边方式可以省一次遍历
         minNum = nextSmaller + 1
        if minNum > 0:
            for i in range(0,len(a)):
                a[i] += minNum 
        
        return a

分析

  • 时间复杂度：O(N)，其中 N 是字符串 S 的长度。

  • 空间复杂度：O(N)。

虽然算法复杂度和官方题解同样是O(n)， 但是第二种思路多了两个遍历（min函数 与for循环）算法复杂度为 3n(感谢 @瞌睡 指出)， 但是第二种思路多了次遍历（for循环偏移）算法复杂度为 2n，而且代码也不够简洁优雅。 这种写法不值得提倡，但提供了另外一种思考角度，拓展下思维还是不错的。