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"。

思路：通过观察，所有的'I'都是从左到右，依次增大，所有的'D'从右到左，依次增大，最大的位置放中间数，即可满足条件，所以一次循环即可
代码：

public int[] diStringMatch(String S) {
    int len = S.length();
    int[] arr = new int[len + 1];
    int j = 0, k = len;
    for(int i = 0; i < len; i++) {
        if(S.charAt(i) == 'I') arr[i] = j++;
        else arr[i] = k--;
    }
    arr[len] = k;
    return arr;
}

用时3ms,时间复杂度O(N)，空间复杂度O(N)N为S的长度。
总结:先观察特征值，想好思路然后解题。