[Swift]LeetCode42. 接雨水 | Trapping Rain Water

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9903130.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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.

[Swift]LeetCode42. 接雨水 | Trapping Rain Water
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

[Swift]LeetCode42. 接雨水 | Trapping Rain Water

上面是由数组 [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 在迭代期间，但现在我们可以使用2个指针在一次迭代中完成，在两者之间切换。$

算法

Initialize
While
- If
- If $height[left] >= left_max$
  - Else add $ans$
  - Add 1 to
- Else

 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 += 1
15             } else {
16                  if height[rightPointer] > rightMax {
17                     rightMax = height[rightPointer]
18                 } else {
19                     trappedWater += rightMax - height[rightPointer]
20                 }
21                 rightPointer -= 1
22             } 
23         }
24         return trappedWater
25     }
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..<height.count {
 8       if maxL < height[i] {
 9         maxL = height[i]
10       }
11       leftMax.append(maxL)
12       if maxR < height[height.count - 1 - i] {
13         maxR = height[height.count - 1 - i]
14       }
15       rightMax.append(maxR)
16     }
17     rightMax.reverse()
18     var result = 0
19     for i in 0..<height.count {
20       let wall = max(min(leftMax[i], rightMax[i]), height[i])
21       result += wall - height[i]
22     }
23     return result
24   }
25 }

【暴力破解】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<Int>(repeating: 0, count: height.count)
 8         var result = 0
 9         var maxR = 0
10         
11         for i in height.enumerated().reversed() {
12             if height[i.offset] > maxR {
13                 maxR = i.element
14                 rights[i.offset] = maxR
15             }else {
16                 rights[i.offset] = maxR
17             }
18         }
19         
20         for i in 0..<height.count {
21             if height[i] > maxL {
22                 maxL = height[i]
23             }
24             result += max(min(maxL, rights[i]) - height[i],0)
25         }
26         
27         
28         return result
29     }
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..<height.count {
10             leftMax[i] = max(leftMax[i - 1], height[i])
11         }
12         
13         rightMax[height.count - 1] = height[height.count - 1]
14         for i in (0..<height.count - 1).reversed() {
15             rightMax[i] = max(rightMax[i + 1], height[i])
16         }
17     
18         for i in 1..<height.count - 1 {
19             res += min(leftMax[i], rightMax[i]) - height[i]
20         }
21         
22         return res
23     }
24 }

【使用堆栈】64ms

 1 class Solution {
 2     func trap(_ height: [Int]) -> Int {
 3         var stack = Stack<Int>()
 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                     break
15                 }
16                 
17                 let distance = current - stack.peek() - 1
18                 
19                 let height = min(height[current], height[stack.peek()]) - height[top]
20                 
21                 ans += distance * height
22             }
23             stack.push(current)
24             current += 1
25         }
26         
27         return ans
28     }
29 }
30 
31 class Stack<T> {
32     private var arr = [T]()
33     
34     var isEmpty: Bool {
35         return arr.isEmpty
36     }
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 }

[Swift]LeetCode42. 接雨水 | Trapping Rain Water

相关推荐