Jamzen的技术博客
0%

LeetCode.接雨水

发表于 分类于 Valine：

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

  • 示例 1：
    输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
    输出：6
  • 示例 2：
    输入：height = [4,2,0,3,2,5]
    输出：9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
object Trap {
  def main(args: Array[String]): Unit = {
    println(trap(Array(4, 2, 0, 3, 2, 5)))
    println(trap(Array(0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1)))

    println(trap2(Array(4, 2, 0, 3, 2, 5)))
    println(trap2(Array(0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1)))

    println(trap3(Array(4, 2, 0, 3, 2, 5)))
    println(trap3(Array(0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1)))
  }

  /**
   * 时间复杂度O(n^2),空间复杂度O(1)
   */
  def trap(height: Array[Int]): Int = {
    var res = 0
    for (i <- 0 until height.size) {
      var lMax = 0
      var rMax = 0
      for (j <- i until height.size) {
        rMax = Math.max(rMax, height(j))
      }

      for (j <- i to 0 by -1) {
        lMax = Math.max(lMax, height(j))
      }
      res += Math.min(lMax, rMax) - height(i)
    }
    res
  }
  /**
   * 时间复杂度O(n),空间复杂度O(n)
   */
  def trap2(height: Array[Int]): Int = {
    if (height.length <= 2) return 0
    var res = 0
    val lArray = new Array[Int](height.size)
    val rArray = new Array[Int](height.size)
    lArray(0) = height(0)
    rArray(height.size - 1) = height(height.size - 1)

    for (i <- 1 until height.size) {
      lArray(i) = Math.max(height(i), lArray(i - 1))
    }

    for (i <- height.size - 2 to 0 by -1) {
      rArray(i) = Math.max(height(i), rArray(i + 1))
    }

    for (i <- 0 until height.size) {
      res += Math.min(lArray(i), rArray(i)) - height(i)
    }
    res
  }

  /**
   * 时间复杂度O(n),空间复杂度O(1)
   */
  def trap3(height: Array[Int]): Int = {
    if (height.length <= 2) return 0
    var l = 0
    var r = height.size - 1
    var lMax = height(l)
    var rMax = height(r)
    var res = 0
    while (l < r) {
      res += Math.min(lMax, rMax)
      if (height(l) < height(r)) {
        res -= height(l)
        l += 1
        lMax = Math.max(lMax, height(l))
      } else {
        res -= height(r)
        r -= 1
        rMax = Math.max(rMax, height(r))
      }
    }

    res
  }

  /**
   * 单调栈写法
   */
  def trap4(height: Array[Int]): Int = {
    if (height.length <= 2) return 0
    var res = 0

    res
  }
}