★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]Output: 6
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6
【双指针】12ms
我们可能会想到在一次迭代中做某种方式，而不是单独计算左右部分。 从图中的动态编程方法来看，只要注意right_max [ i ] > left_max [ i ]right_max[一世]>left_max[一世] （从元素0到6），被困水取决于left_max，类似情况 left_max [ i ] > right_max [ i ]left_max[一世]>right_max[一世]（从要素8到11）。 因此，我们可以说如果一端有一个较大的条（如右图），我们可以确保被困的水将取决于当前方向（从左到右）的条形高度。 一旦我们发现另一端（右）的条形较小，我们就会开始以相反的方向（从右到左）进行迭代。 我们必须坚持left_maxleft_max 和 right_maxright_max 在迭代期间，但现在我们可以使用2个指针在一次迭代中完成，在两者之间切换。
算法
- Initialize \text{left}left pointer to 0 and \text{right}right pointer to size-1
- While \text{left}< \text{right}left<right, do:
- If \text{height[left]}height[left] is smaller than \text{height[right]}height[right]
- If height[left]>=left_maxheight[left]>=left_max, update left_maxleft_max
- Else add left_max−height[left]left_max−height[left] to \text{ans}ans
- Add 1 to \text{left}left.
- Else
- If height[right]>=right_maxheight[right]>=right_max, update right_maxright_max
- Else add right_max−height[right]right_max−height[right] to \text{ans}ans
- Subtract 1 from \text{right}right.
1 class Solution { 2 func trap(_ height: [Int]) -> Int { 3 var leftMax = 0, rightMax = 0 4 var leftPointer = 0, rightPointer = height.count - 1 5 var trappedWater = 0 6 7 while leftPointer < rightPointer { 8 if height[leftPointer] < height[rightPointer] { 9 if height[leftPointer] > leftMax {10 leftMax = height[leftPointer]11 } else {12 trappedWater += leftMax - height[leftPointer]13 }14 leftPointer += 115 } else {16 if height[rightPointer] > rightMax {17 rightMax = height[rightPointer]18 } else {19 trappedWater += rightMax - height[rightPointer]20 }21 rightPointer -= 122 } 23 }24 return trappedWater25 }26 } 【动态编程】 16ms
1 class Solution { 2 func trap(_ height: [Int]) -> Int { 3 var leftMax = [Int]() 4 var rightMax = [Int]() 5 var maxL = 0 6 var maxR = 0 7 for i in 0.. 【暴力破解】28ms
1 class Solution { 2 func trap(_ height: [Int]) -> Int { 3 if height.count <= 0 { 4 return 0 5 } 6 var maxL = height[0] 7 var rights : Array = Array (repeating: 0, count: height.count) 8 var result = 0 9 var maxR = 010 11 for i in height.enumerated().reversed() {12 if height[i.offset] > maxR {13 maxR = i.element14 rights[i.offset] = maxR15 }else {16 rights[i.offset] = maxR17 }18 }19 20 for i in 0.. maxL {22 maxL = height[i]23 }24 result += max(min(maxL, rights[i]) - height[i],0)25 }26 27 28 return result29 }30 } 【暴力破解】44ms
1 class Solution { 2 func trap(_ height: [Int]) -> Int { 3 guard height.count > 2 else { return 0 } 4 var res: Int = 0 5 var leftMax = Array(repeating: 0, count: height.count) 6 var rightMax = Array(repeating: 0, count: height.count) 7 8 leftMax[0] = height[0] 9 for i in 1.. 【使用堆栈】64ms
1 class Solution { 2 func trap(_ height: [Int]) -> Int { 3 var stack = Stack () 4 5 var ans = 0 6 7 var current = 0 8 9 while current < height.count {10 while !stack.isEmpty && height[current] > height[stack.peek()] {11 let top = stack.pop()12 13 if stack.isEmpty {14 break15 }16 17 let distance = current - stack.peek() - 118 19 let height = min(height[current], height[stack.peek()]) - height[top]20 21 ans += distance * height22 }23 stack.push(current)24 current += 125 }26 27 return ans28 }29 }30 31 class Stack {32 private var arr = [T]()33 34 var isEmpty: Bool {35 return arr.isEmpty36 }37 38 func peek() -> T {39 return arr.last!40 }41 42 func push(_ t: T) {43 arr.append(t)44 }45 46 func pop() -> T {47 return arr.removeLast()48 }49 }