LeetCode 42 接雨水详解
① 暴力解法
拿到这道题，我们首先看图分析。
不难发现当前位置装水的高度其实和两边高度有关。以索引为 5 的位置为例，最多装 2 个单位水，这取决于对应的左侧最大值和右侧最大值位置。
结论：i 位置处能装多少水取决于它左侧比它大的最大值与右侧比它大的最大值取 min 减去 i 位置高度即可。
公式：
int water = min(leftMax, rightMax) - height[i];
时间复杂度为 O(N^2)，详细思路如下： 遍历一遍数组，当前位置能接的水的高度是左边最大值与右边最大值的 min 减去当前位置高度。累加每单位宽度的雨水面积。
代码如下：
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int totalWater = 0;
for (int i = 1; i < n - 1; i++) {
int leftMax = 0, rightMax = 0;
// 找左边最大值
for (int j = 0; j < i; j++) {
leftMax = max(leftMax, height[j]);
}
// 找右边最大值
for (int j = i + 1; j < n; j++) {
rightMax = max(rightMax, height[j]);
}
// 如果左右最大值有一个小于当前位置高度，则说明不能接雨水
if ((leftMax < height[i]) || (rightMax < height[i])) continue;
// 计算当前位置能接的水量
int water = min(leftMax, rightMax) - height[i];
(water > ) {
totalWater += water;
}
}
totalWater;
}
};
