LeetCode100.7 接雨水

对于这题，有一个非常直观简洁的思路：水量等于柱子围成的体积减去柱子的体积。

首先计算每一个高度的体积，相加即为总体积，减去sum(height)即为水的体积。

class Solution {
public:int trap(vector<int>& height) {int n = height.size();int maxHeight = 0, totalH = 0;for (auto i : height) {totalH += i;maxHeight = max(maxHeight, i);}int i = 0, j = n - 1, sum = 0;for (int h = 1; h <= maxHeight; h++) {while (height[i] < h) i++;while (height[j] < h) j--;sum += (j - i + 1);}return sum - totalH;}
};