Neil coding之路

Have a nice day

0%

Javascript(leetcode#42) Trapping Rain Water

發表於 更新於 分類於 ， Disqus：

Difficult:Hard

題目

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

翻譯

給定 n 個非負整數，表示每個條的寬度為 1 的高程圖，計算下雨後它可以捕獲多少水。

範例

Example 1:
example

1
2
3
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) 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.

Example 2:

1
2
Input: height = [4,2,0,3,2,5]
Output: 9

解題思路

1.左右邊比較大小，較小的一方往前移動。

Solution

Code 1 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var trap = function(height) {
    let [l, r, lmax, rmax, max] = [0, height.length-1, 0, 0, 0];
    while(l < r) {
        if(height[l] <= height[r]) {
            if(height[l] >= lmax) {
                lmax = height[l];
            } else {
                max += lmax-height[l];
            }
            l++;
        } else {
            if(height[r] >= rmax) {
                rmax = height[r];
            } else {
                max += rmax-height[r];
            }
            r--;
        }
        
    }
    return max;
};

Code 2 :

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
var trap = function (height) {
  let start = 0;
  let end = 0;
  let res = 0;
  while (start < height.length) {
    if (height[start] > 0) {
      let sum = 0;
      let secmax = 0;
      let secindex = -1;
      end = -1;
      for (let i = start + 1; i < height.length; i++) {
        if (height[i] >= height[start]) {
          end = i;
          break;
        } else {
          sum += height[i];
          if (height[i] > secmax) {
            secmax = height[i];
            secindex = i;
          }
        }

      }
      if (end != -1) {

        let val = (end - start - 1) * height[start] - sum;
        res += val;

        start = end - 1;
      } else {

        if (secindex - start > 1) {
          let secsum = 0;
          for (let i = start + 1; i < secindex; i++) {
            secsum += height[i];
          }
          let val = (secindex - start - 1) * height[secindex] - secsum;
          res += val;
          start = secindex - 1;
        }
      }

    }

    start++;
  }
  return res;
};