Find Permutation

这题还是属于观察规律的，仔细看很容易发现如果我们有一个栈，每次碰见D，则把当前数压入栈中，指针往前推，碰见I，则全部倒出来加到结果上，最后形成的这个序列就是我们需要的字典序最小序列，另外此题还需要发现上下规律的字符串长度加一就是我们的结果长度

class Solution(object):
    def findPermutation(self, s):
        """
        :type s: str
        :rtype: List[int]
        """
        stack = []
        n = len(s)
        nums = range(2, n + 2)
        stack.append(1)
        cur = 0
        result = []
        for char in s:
            if char == 'I':
                while stack:
                    result.append(stack.pop())
                stack.append(nums[cur])
            else:
                stack.append(nums[cur])
            cur += 1
        while stack:
            result.append(stack.pop())
        return result

这里其实还可以发现栈的应用只是模拟了一个部分倒序的功能，实际上我们可以自己来做这个局部倒序，这样就节省了空间复杂度