942. 增减字符串匹配

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

示例 1：

输出："IDID"
输出：[0,4,1,3,2]

示例 2：

输出："III"
输出：[0,1,2,3]

示例 3：

输出："DDI"
输出：[3,2,0,1]

提示：

1 <= S.length <= 1000
S 只包含字符 "I" 或 "D"。

思路

一开始的思路是初始一个升序数组，逐位有选择交换相邻两个数，但是最终结果并不是整体符合结果的（似乎有一道类似的大小排序的问题，想着直接套用，结果不行）

看了别人的代码，非常的简洁
取一个最大数一个最小数，依条件不断向中间数接近

最后所有数字排列的感觉看起来，大致应该是类似于一个有渐近线的函数。摆头看应该像龙卷风
举个例子

10
        9
            8
                    7
                        6
                                        5
                                    4
                                3
                            2
                1
    0

两个指针一个指的是当前可用最小值smallNum，一个是当前可用最大值bigNum。
当S[i]为D时，即此时需要减少，那么向结果集中加入bigNum，则后续所有值均小于bigNum，满足条件
同理有S[i]为I时，即此时需要增加，那么向结果集中加入smallNum，则后续所有值均大于smallNum，满足条件

性能分析

遍历一遍即可，时间复杂度为O(N)。空间复杂度为O(1)

具体代码

vector<int> diStringMatch(string S) {
    int smallNum = 0;
    int bigNum = S.length();
    int len = bigNum;
    vector<int> res;
    
    for(int i = 0; i < len; i++){
        if(S[i] == 'I'){
            res.push_back(smallNum++);
        }
        else{
            res.push_back(bigNum--);
        }
    }
    res.push_back(smallNum);
    return res;
}