演算法

1// O(n²): for every cell, scan both sides for the tallest wall.
2function trapBrute(h: number[]): number {
3  let total = 0;
4  for (let i = 0; i < h.length; i++) {
5    let left = 0, right = 0;
6    for (let j = 0; j <= i; j++) left = Math.max(left, h[j]);
7    for (let j = i; j < h.length; j++) right = Math.max(right, h[j]);
8    total += Math.min(left, right) - h[i];
9  }
10  return total;
11}
12 
13// O(n) time, O(n) space: precompute both walls.
14function trapPrefix(h: number[]): number {
15  const n = h.length, leftMax = new Array(n).fill(0), rightMax = new Array(n).fill(0);
16  for (let i = 0; i < n; i++) leftMax[i] = Math.max(i ? leftMax[i - 1] : 0, h[i]);
17  for (let i = n - 1; i >= 0; i--) rightMax[i] = Math.max(i < n - 1 ? rightMax[i + 1] : 0, h[i]);
18  let total = 0;
19  for (let i = 0; i < n; i++) total += Math.min(leftMax[i], rightMax[i]) - h[i];
20  return total;
21}
22 
23// O(n) time, O(1) space: move inward from the lower side, whose wall is known.
24function trapTwoPointers(h: number[]): number {
25  let lo = 0, hi = h.length - 1, leftWall = 0, rightWall = 0, total = 0;
26  while (lo <= hi) {
27    if (h[lo] <= h[hi]) {
28      leftWall = Math.max(leftWall, h[lo]);
29      total += leftWall - h[lo++];
30    } else {
31      rightWall = Math.max(rightWall, h[hi]);
32      total += rightWall - h[hi--];
33    }
34  }
35  return total;
36}
37 
38// O(n): a stack of falling walls; each taller wall fills one layer per pop.
39function trapStack(h: number[]): number {
40  const stack: number[] = [];
41  let total = 0;
42  for (let i = 0; i < h.length; i++) {
43    while (stack.length && h[stack[stack.length - 1]] < h[i]) {
44      const bottom = stack.pop()!;
45      if (!stack.length) break;
46      const left = stack[stack.length - 1];
47      total += (Math.min(h[left], h[i]) - h[bottom]) * (i - left - 1);
48    }
49    stack.push(i);
50  }
51  return total;
52}