★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（）

➤GitHub地址：

➤原文地址： 

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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

---

给定只含 "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. 1 <= S.length <= 1000
2. S 只包含字符 "I" 或 "D"。

---

68ms

1 class Solution { 2     func diStringMatch(_ S: String) -> [Int] { 3       let N = S.count 4       var min = 0 5       var max = N 6        7       var res : [Int] = [] 8        9       for c in S {10         if c == "I" {11           res.append(min)12           min += 113         } else if c == "D" {14           res.append(max)15           max -= 116         }17       }18       assert(min == max);19       res.append(min)20       21       return res22     }23 }

---

84ms

1 class Solution { 2     func diStringMatch(_ S: String) -> [Int] { 3         let array = Array(0...S.count) 4          5         var left = 0 6         var right = S.count 7          8         var result = [Int]() 9         for char in S {10             if char == "I" {11                 result.append(array[left])12                 left += 113             } else if char == "D" {14                 result.append(array[right])15                 right -= 116             }17         }18         result.append(array[left])19         20         return result21     }22 }

---

88ms

1 class Solution { 2     func diStringMatch(_ S: String) -> [Int] { 3          4         var out:[Int] = [] 5          6         var i = 0 7         var d = S.count 8          9         for c in S {10             11             if c == "I" {12                 13                 out.append(i)14                 i += 115                 16             } else {17                 out.append(d)18                 d -= 119             }20             21         }22         23         if S.last! == "I" {24              out.append(i)25                 i += 126         } else {27             out.append(d)28                 d -= 129         }30         31         return out32     }33 }

---

120ms

1 class Solution { 2     func diStringMatch(_ S: String) -> [Int] { 3         var arr:[Int] = [] 4         var min = -1, max = S.count + 1 5         for c in S { 6             if c == "I" { 7                 min+=1 8                 arr.append(min) 9             } else {10                 max-=111                 arr.append(max)12             }13         }14         arr.append(min+1)15         return arr16     }17 }

---

312ms

1 class Solution { 2      3     struct HeapElement { 4         let idx: Int 5         let value: Int 6         init(_ idx: Int, _ value: Int) { 7             self.idx = idx 8             self.value = value 9         }10     }11     12     func diStringMatch(_ S: String) -> [Int] {13         let N = S.count14         var heap: [HeapElement] = [HeapElement(0,0)]15         var prevValue = 016         var idx = 117         for ch in S {18             if ch == "I" {19                 prevValue += 120             } else {21                 prevValue -= 122             }23             heap.append(HeapElement(idx, prevValue))24             var curInd = heap.count - 125             while heap[curInd].value < heap[(curInd - 1) / 2].value && curInd > 0 {26                 let parentInd = (curInd - 1) / 227                 heap.swapAt(curInd, parentInd)28                 curInd = parentInd29             }30             idx += 131         }32         33         var result: [Int] = Array(repeating: 0, count: N + 1)34         prevValue = 035         while !heap.isEmpty {36             heap.swapAt(0, heap.count - 1)37             let element = heap.removeLast()38             result[element.idx] = prevValue39             prevValue += 140             var curInd = 041             while (2*curInd + 1 < heap.count && heap[curInd].value > heap[2*curInd + 1].value) || 42             (2*curInd + 2 < heap.count && heap[curInd].value > heap[2*curInd + 2].value) {43                 var childInd = 2*curInd + 144                 if 2*curInd + 2 < heap.count {45                     if heap[childInd].value > heap[2*curInd + 2].value {46                         childInd = 2*curInd + 247                     }48                 }49                 heap.swapAt(curInd, childInd)50                 curInd = childInd51             }52         }53         return result54     }55 }

---

2096ms

1 class Solution { 2     func diStringMatch(_ S: String) -> [Int] { 3         var n:Int = S.count + 1 4         var ret:[Int] = [Int](repeating: 0,count: n) 5         var v:Int = n - 1 6         var pre:Int = 0 7         for i in 0..<(n - 1) 8         { 9             if S[i] == "D"10             {11                 for j in (pre...i).reversed()12                 {13                     ret[j] = v14                     v -= 115                 }16                 pre = i + 117             }18         }19         for j in (pre...(n - 1)).reversed()20         {21             ret[j] = v22             v -= 123         }24         return ret25     }26 }27 28 extension String {29     //subscript函数可以检索数组中的值30     //直接按照索引方式截取指定索引的字符31     subscript (_ i: Int) -> Character {32         //读取字符33         get {
   return self[index(startIndex, offsetBy: i)]}34     }35 }