时间轴

2025-11-05

init

题目：

P42 接雨水

https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-interview-150

每次向最低的地方灌水，和下面这个三维的思想类似，也可以说是简化版本。

参考：

P407 接雨水 II

https://even629.com/posts/407/

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
#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
	int trap(vector<int> &height)
	{
		int n = height.size();
		int left_boundary = 0, right_boundary = n - 1;
		int lower;
		int rain = 0;
		while (left_boundary < right_boundary) {
			lower = std::min(height[left_boundary],
					 height[right_boundary]);
			// 向边界最低的地方灌水
			if (height[left_boundary] < height[right_boundary]) {
				if (height[left_boundary + 1] <
				    height[left_boundary]) {
					rain += height[left_boundary] -
					       height[left_boundary + 1];
					height[left_boundary + 1] =
						height[left_boundary];
				}
				left_boundary++;

			} else {
				if (height[right_boundary - 1] <
				    height[right_boundary]) {
					rain += height[right_boundary] -
					       height[right_boundary - 1];
					height[right_boundary - 1] =
						height[right_boundary];
				}
				right_boundary--;
			}
		}
		return rain;
	}
};