42. 接雨水
知识点
数组最大值
vector<int> p = {2, 1, 3, 5, 4}; vector<int>::iterator a = max_element(p.begin(), p.end());
返回的是迭代器，寻值需要*a
数组最大值的索引
vector<int> p = {2, 1, 3, 5, 4}; vector<int>::iterator a = max_element(p.begin(), p.end()); cout<<a-p.begin();
小白解法
class Solution { public: int trap(vector<int> &height) { int N = height.size(); int left = 0; int right = N - 1; vector<int>::iterator p = max_element(height.begin(), height.end()); int max = p - height.begin(); int sum = 0; while (left < max) { int tmp = left + 1; while (height[left] > height[tmp]) { sum += height[left] - height[tmp]; tmp++; } left = tmp; } while (right > max) { int tmp = right - 1; while (height[right] > height[tmp]) { sum += height[right] - height[tmp]; tmp--; } right = tmp; } return sum; } };
先找到最大值，然后分别从两边往最高点遍历：如果下一个数比当前数小，说明可以接到水。
动态规划
class Solution { public: int trap(vector<int> &height) { int N = height.size(); if (!N) { return 0; } vector<int> left_max_list(N), right_max_list(N); left_max_list[0] = height[0]; right_max_list[N - 1] = height[N - 1]; for (int i = 1; i < N; i++) { left_max_list[i] = max(height[i], left_max_list[i - 1]); } for (int i = N - 2; i >= 0; i--) { right_max_list[i] = max(height[i], right_max_list[i + 1]); } int sum = 0; for (int i = 0; i < N; i++) { sum += min(left_max_list[i], right_max_list[i]) - height[i]; } return sum; } };
注意vector<int> left_max_list(N),right_max_list(N);有(N)，标注容器大小时可以直接赋值，赋值需要push_back()
该解法通过分别寻找每个元素向左和向右扫描时左边和右边的最大高度。然后选每个位置向左向右的最小值减去该位置高度值。
单调栈
class Solution { public: int trap(vector<int> &height) { int N = height.size(); int sum = 0, current = 0; stack<int> stk; while (current < N) { while (!stk.empty() && height[current] > height[stk.top()]) { int top = stk.top(); stk.pop(); if (stk.empty()) { break; } int distance = current - stk.top() - 1; int bounded_height = min(height[current], height[stk.top()]) - height[top]; sum += distance * bounded_height; } stk.push(current++); } return sum; } };
们仔细观察蓝色的部分，可以和括号匹配类比下。每次匹配出一对括号（找到对应的一堵墙），就计算这两堵墙中的水。
总体的原则是：
1.当前高度小于等于栈顶高度，入栈，指针后移。
2.当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移
双指针
class Solution { public: int trap(vector<int> &height) { int N = height.size(); int left = 0, right = N - 1; int sum = 0; int max_left = 0, max_right = 0; while (left < right) { if (height[left] < height[right]) { if (height[left] > max_left) { max_left = height[left]; } else { sum += max_left - height[left]; } left++; } else { if (height[right] > max_right) { max_right = height[right]; } else { sum += max_right - height[right]; } right--; } } return sum; } };
该解法是对动态规划解法的空间复杂度优化，从动态规划方法中可以发现right_max[i]>left_max[i]时，积水高度由left_max决定，反之亦然。可以认为如果右端有更高的墙时，积水高度依赖当前位置左边的left_max。当发现右侧的墙不是最高的时候，则从相反方向遍历（从右到左）。
感悟
双指针法太妙了！
