942. DI String Match

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 <= S.length <= 10000
S only contains characters "I" or "D".

这题主要是给出一个整型数组的字符串形式，表示着数字的递增和递减关系，然后给出一个整型数组满足该条件，并且元素是从1开始至N-1不能重复。

这题说实话看起来没那么简单，我也想了好一会儿，然后想出了一个能解决的算法，但是看上去没那么直接。

我这里的解法是，初始化结果的数组，并且首元素的值是字符串的长度，并且初始化两个变量分别也赋值为字符串长度，分别表示递增分配的起始值和递减分配的起始值。

然后扫描字符串，假设是D，则取递减分配的起始值-1,添加至结果数组结尾，并且更新递减的起始值;递增一样。这样能保证分配的值都不一样并且由于递减的分配值永远小雨递增的分配值，所以永远会满足条件。

当然这种解法不能保证最小值为0,所以我们最后还需要减去递减的起始值，这样所有的值减去该值之后，就成为从0开始的一个数组了。代码如下：

class DIStringMatch : public Solution {
public:
    void Execute() {
        auto res = diStringMatch("DDIDDDDIID");
    }
    vector<int> diStringMatch(string S) {
        vector<int> out;
        out.resize(S.size() + 1);
        out[0] = int(S.size());
        int sl = out[0], bl = out[0];

        for (std::size_t i = 0; i < S.size(); i++) {
            S[i] == 'D' ? out[i + 1] = --sl : out[i + 1] = ++bl;
        }
        for (std::size_t i = 0; i < out.size(); i++) {
            out[i] -= sl;
        }
        return out;
    }
};

---

之后想了个更好的办法，可以去掉最后一步的循环，虽然起始对于时间复杂度影响不大。

之前的算法考虑到了两个元素之间的关系，新的算法根本就不考虑这层关系，简单的说，假设当前是I，则放最小的元素进去，同时更新最小的元素值;反之也一样。由于放入了最小的元素进去，后面无论放任何元素进去都是递增的。最后需要把最小的元素或者最大的元素放入数组结尾即可。

vector<int> diStringMatch(string S) {
        vector<int> out;
        out.reserve(S.size() + 1);
        int sl = 0, bl = int(S.size() - 1);

        for (std::size_t i = 0; i < S.size(); i++) {
            S[i] == 'D' ? out.push_back(bl--) : out.push_back(sl++);
        }
        out.push_back(sl);

        return out;
    }