題目連結：
題目意譯：
給定一字串 S ，其只包含 'I'（Increase，增加） 和 'D' （Decrease，減少），令 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 ≦ S.length ≦ 10000
S 只包含字元 'I' 或 'D' 。
範例測資：
範例 1：
輸入： "IDID"
輸出： [0,4,1,3,2]
範例 2：
輸入： "III"
輸出： [0,1,2,3]
範例 3：
輸入： "DDI"
輸出： [3,2,0,1]
解題思維：
這題有個巧妙的解法：
令 L = 0 、 U = N ，且 answer 為答案數列。
對於 S 中每個字元 S[i]：
如果 S[i] 為 'I'，則
將 L 之值複製貼上到 answer 最後面
L += 1
反之 S[i] 為 'D'，則
將 U 之值複製貼上到 answer 最後面
U -= 1
掃完 S 之後，將 L （或是 U）之值複製貼上到 answer 最後面。此時 answer 即是所求。
為什麼上面的作法會生出一個解呢？
我們定義 M 為最後加入到 answer 的數字。
然後我們將 answer 分為三個子序列：
一個是 X = [0, 1, ……, M - 1]、
一個是 Y = [N, N - 1, ……, M + 1]。
最後一個即是 M 本身。
例如 answer = [0, 4, 1, 3, 2]，則
X = [0, 1]、
Y = [4, 3]、
M = 2
可以看到 X 的所有元素皆小於 Y 的任一元素 、 Y 的所有元素皆大於 X 的任一元素。再加上 X 為嚴格遞增、Y 為嚴格遞減。
因此當我們將 'I' 對應到 X 的某個元素時（如上面的演算法之步驟，將 L 貼到 answer 後面），不管接下來的數字是 X 、 Y 的還是 M 之值，都會符合 'I' ——增加。
也就是說 answer[i] 若為 X[j]，則不管 answer[i + 1] 為 X[j + 1] 、 Y[k] 或是 M ，都符合 answer[i] < answer[i + 1]。
同樣地當我們將 'D' 對應到 Y 某個元素時（如上面的演算法之步驟，將 U 貼到 answer 後面），不管接下來的數字是 Y 、 X 的還是 M 之值，都會符合 'D' ——減少。
也就是說 answer[i] 若為 Y[j]，則不管 answer[i + 1] 為 Y[j + 1] 、 X[k] 或是 M ，都符合 answer[i] > answer[i + 1]。
因為上述理由，該演算法才能得到一個合法的解。
不過值得注意的是，本題並沒有保證唯一解，此演算法只是能求出其中一者而已。可以看到
長度為 N 之字串 S 的可能種類為 2 ^ N ，而 N + 1 個數字之排列為 (N + 1)!。
前者之數量級為 log(2 ^ N) = N × log(2) = O(N)、
後者之數量級為 log((N + 1)!) = O(N × log(N)) （參見斯特靈公式（Stirling's Formula）之維基頁面）
很明顯地，前者的成長速度小於後者。所以對於足夠大的 N 值，長度為 N 的字串 S 可能會有多組符合的 0 ～ N 之排列數組。
例如 N = 2 的時候就可以發現：
字串 S 有四種 ，II 、 ID 、 DI 以及 DD。
而 0 ～ 2 之排列有以下六種：
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
可以看到 0 2 1 以及 1 2 0 都符合 ID 、 1 0 2 、 2 0 1 都屬於 DI。而我們的演算法會求出 ID 中的 0 2 1 以及 DI 中的 2 0 1。
因此證實了我們的演算法求得的不是唯一解。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
