1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public String smallestNumber(String pattern) {
        StringBuilder ans = new StringBuilder(), stack = new StringBuilder();
        for (int i = 0; i <= pattern.length(); i++) {
            stack.append((char) (i + '1'));
            if (i == pattern.length() || pattern.charAt(i) == 'I') {
                ans.append(stack.reverse());
                stack = new StringBuilder();
            }
        }
        return ans.toString();
    }
}

这个是观察出来的一个特征. 如果一直是IIII…, 那么我们1234…这样排就好了. 如果突然碰到一个D呢? 比如IIIDI, 我们本来好好的123准备填4的时候发现是个D, 这说明要填4的这个位置要比它之后的位置大, 如果我们在这里填了4, 那没有数字比4小了, 因为比4小的1, 2, 3都被我们用过了. 于是我们只能填5然后填4. 等等如果是这样呢? IIIDDI. 前面1, 2, 3没什么好说的, 按照我们之前的讨论, 下一个位置要填5, 然后填4, 但是最后一个是D, 等于是这之后要填一个比4小的数字, 又回到了这个问题, 比4小的数字1, 2, 3都被我们用过了. 所以1, 2, 3之后不能填5, 得填6, 然后4的位置不能填4, 得填5, 之后5后面填一个4就完美了. 这样我们就发现规律了. 本来应该是4, 因为有一个D我们填了5, 4; 本来应该填4, 因为有两个D我们填了6, 5, 4; n个D呢? 我们应该填4 + n, 3 + n…4. 我们发现其实是从4填到n + 4然后reverse. 那么如何判断有多少连续的D呢? 因为一旦遇到I, 我们这个pattern就结束了. 我们看I, 如果遇到I, 我们就知道需要把之前的这些数字给reverse一下. 比如IIIDDDIDD: 一开始是填1, 2, 3然后发现是D, 保留4, 然后继续发现还是D, 保留5, 然后继续, 发现又是D, 保留6, 然后走发现是I, 那么就可以把4, 5, 6带上这里的7给reverse, 这样就变成1, 2, 3, 7, 6, 5, 4. 之后走发现又是D, 保留8, 然后发现又是D, 保留9, 然后发现到头了, 此时我们反转之前的保留, 结果变为1, 2, 3, 7, 6, 5, 4, 9, 8.

最终的规律就是, 每一个位置的数字都是固定的也就是1, 2, 3, 4..9. 问题就是如果有一个或多个D的出现, 我们要保留一些数字, 直到I的出现或者到头, 我们把这些保留的数字反转然后append到结果中去. 这样就是第5行干的事情, 不管现在是I还是D, 先保留, 如果是I, 那直接反转进入结果, 毕竟一个字符反转还是自己, 如果是D, 那就保留在了stack中, 一直遇到I, 此时我们把I位置对应的数字压入栈然后反转放进ans中. 注意I这里对应的数字也是参与反转的. 因为如果有n给连续的D, 那么就牵扯n + 1个数字, 因为D的规定就是该位置比下一个位置大. 因此I出现的位置对应的数字也应该是被包含进反转. 这也就是第5行不管什么, 先压进来再说. 如果是单个I, 那可以直接放走.

时间复杂度:O(n) 一个数字进stack出stack最多一次.
空间复杂度:O(n) 因为用了stack, 给的pattern可能全是D.