Given a string S that only contains "I" (increase) or "D" (decrease), let N = S.length.

Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:

• If S[i] == "I", then A[i] < A[i+1]
• If S[i] == "D", then A[i] > A[i+1]

Example 1:

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

Example 2:

Input: "III"
Output: [0,1,2,3]

Example 3:

Input: "DDI"
Output: [3,2,0,1]

Note:

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

题目大意：

  给定一个字符串数组S,长度为n。根据S构造一个数组A,A的长度为n+1,且A的值为0-n。
  若S[i]为'I',则与之对应的A[i]的值比右边所有的值要小;若为[D]则相反。

解题思路：

  根据题目大意可知，从左往右的值必定是最大/最小，取决于出现的是[D]还是[I]，然后再逐渐减小/增大。可以设置两个变量max、min分别表示变化过程。
  若S[i]==[D]，则当前位置A[i]值为max，然后max自减。
  若S[i]==[I]，则当前位置A[i]值为min，然后min自增。
  △N=max-min，max初值为n，min初值为0，开始时△N=n。每遍历一个字符，△N-1，一共有n个字符，当S遍历结束时，则有△N=0,即max = min,所以最后一个A[n-1]的值为max或min。

解题代码：

class Solution {
public:
    vector<int> diStringMatch(string S) {
        int max=S.size(), min = 0;
        vector<int> result;
        for(char ch : S)
            result.push_back(ch == 'D'?max--:min++);
        result.push_back(max);
        return result;
    }
};