① 这个题不要想着去求最后接出来的雨水长啥样，然后再来算面积。就比如示例，index 1 与 index 3 组成一个坑，可以求得一个面积，index 3 和 index 7 又组成一个坑 ......。这样子不是太好写，虽然也可以：用单调栈求出 index i 右边第一个大于等于它的数的下标 bigRig[i] (没有则为 -1)，然后就可以与 index i 组成一个坑，但会漏掉一种情况，即 4 2 3 或者 7 5 0 0 6 这种情况，即对于 bigRig[i] == -1 的情况，需要继续向右找到第一个 bigRig[j] == -1，然后 i 与 j 组成一个坑。。。。时间复杂度 O(n)，空间复杂度 O(n).
② 第二种想法：对于每个 index i，它对答案所做出的贡献是 min( index i 左边最高的高度, index i 右边最高的高度) - height[i]，，，有了这一想法，就很容易写了。时间 O(n)，空间 O(n)
③ 对想法二的优化：可优化为 时间 O(n)，空间 O(1).. (见代码与代码注释)
// ① class Solution { public: int trap(const vector<int>& height) { vector<int> bigRig(height.size(), -1); // 右边第一个比他大的数 vector<int> preSum; // 前缀和 preSum.emplace_back(0); // preSum[i + 1] 表示 0~i 的前缀和 stack<int> stk; // 单调栈 for(int i = 0; i < height.size(); ++ i) { preSum.emplace_back(preSum.back() + height[i]); while(!stk.empty() && height[stk.top()] <= height[i]) { bigRig[stk.top()] = i; stk.pop(); } stk.push(i); } int ret = 0; for(int i = 0; i < height.size(); ++ i) { if(bigRig[i] != -1) { ret += height[i] * (bigRig[i] - i) - (preSum[bigRig[i]] - preSum[i]); i = bigRig[i] - 1; } else { int j = i + 1; if(j == height.size()) break; // 注意 break while(j < height.size() && bigRig[j] != -1) ++ j; ret += height[j] * (j - i) - (preSum[j + 1] - preSum[i + 1]); i = j - 1; } } return ret; } };
// ②
class Solution { public: int trap(const vector<int>& height) { vector<int> lefMax(height.size(), 0); vector<int> rigMax(height.size(), 0); lefMax[0] = height[0]; rigMax.back() = height.back(); for(int i = 1; i < height.size(); ++ i) { lefMax[i] = max(lefMax[i - 1], height[i]); } for(int i = height.size() - 2; i >= 0; -- i) { rigMax[i] = max(rigMax[i + 1], height[i]); } int ret = 0; for(int i = 1; i < height.size() - 1; ++ i) { int tmp = min(lefMax[i - 1], rigMax[i + 1]) - height[i]; ret += (tmp > 0 ? tmp : 0); } return ret; } };
// ③
class Solution { public: int trap(const vector<int>& height) { if(height.empty()) return 0; int l = 0, r = height.size() - 1; int lefMax = 0, rigMax = 0; int ret = 0; /* * 第一: 为什么 height[l] < height[r] 就表示 lefMax < rigMax ? * * 假设, 上次的 lefMax < rigMax, 那么 ++l 后, height[l] < height[r], * 此时 lefMax < rigMax 成立是显然的. * * 假设, 上次的 lefMax > rigMax, --r 后, height[l] < height[r], * 此时的 rigMax 得到更新, 并且 rigMax == height[r], 这是显然的, 因为上一次 * 导致 -- r 执行的原因就是, height[l] > height[r]. (height[l] > height[r + 1] && height[l] < height[r]) * 同样的道理, lefMax == height[l], 所以 height[l] < height[r], * 就表示 lefMax < rigMax. * * * 然后,对于 i 这个位置来说, 它对答案的贡献是: min(左的最高, 右的最高) - height[i] * 注意, 是 min(). * 所以当 height[l] < height[r] 时, 区间 [l + 1, r) 是否还有比 lefMax * 更大的值已经没有意义了. 直接将 l 的贡献计入答案即可. * */ while(l < r) { lefMax = max(lefMax, height[l]); rigMax = max(rigMax, height[r]); if(height[l] < height[r]) { ret += lefMax - height[l]; ++ l; } else { ret += rigMax - height[r]; -- r; } } return ret; } };