Given a stringSthat only contains "I" (increase) or "D" (decrease), letN = S.length.

Return any permutationAof[0, 1, ..., N]such that for alli = 0, ..., N-1:

• IfS[i] == "I", thenA[i] < A[i+1]
• IfS[i] == "D", thenA[i] > A[i+1]

Note:

1. 1 <= S.length <= 10000
2. S only contains characters"I"or"D".

Example 1:

Input: "IDID"
Output: [0,4,1,3,2]

这道题限定了返回的数字必须在0到N-1之间，所以在给数组的元素赋值的时候，必须保证大小关系的同时，还要保证有合适的数字可用。比如输入如果是“DDD“ ，输出应该是[3, 2, 1, 0]，如果第一个数字赋值为0，第二个则必须小于0，不符合题目要求。

为了保证赋值的数字永远符合要求，在遇到I(increase)的时候，则使用当前可用的最小的数字，遇到D(decrease)的时候，使用当前最大的数字，这样可以保证对后面的字符，永远有足够符合要求的数字

class Solution {
    public int[] diStringMatch(String S) {
        if(S == null || S.length() == 0)
            return new int[] {0};

        int n = S.length();
        int[] res = new int[n + 1];
        int low = 0;
        int high = n;

        for(int i = 0; i < n; i++) {
            if(S.charAt(i) == 'I') {
                res[i] = low++;
            } else {
                res[i] = high--;
            }
        }

        res[n] = high;

        return res;
    }
}