LeetCode42. [H]接雨水（动态规划、单调栈、双指针*）

LeetCode42.接雨水

思路

对于每一个柱子，他所能接的雨水就是左边最高的柱子和右边最高的柱子小的那一个再减去自己的高度。
既：min(leftMax,rightMax)−height
解题方法

动态规划

官方题解（截取）：


创建两个长度为 n 的数组 leftMax 和 rightMax。对于 0≤iheight[top]，则得到一个可以接雨水的区域，该区域的宽度是 i−left−1，高度是 min(height[left],height)−height[top]，根据宽度和高度即可计算得到该区域能接的雨水量。</ul>代码：

1. class Solution {
2. public:
3.     int trap(vector<int>& height) {
4.         int n = height.size();
5.         if (n == 0) {
6.             return 0;
7.         }
8.         vector<int> leftMax(n);
9.                 //获取每个元素左边的最大值（从左到右遍历）
10.         leftMax[0] = height[0];
11.         for (int i = 1; i < n; ++i) {
12.             leftMax[i] = max(leftMax[i - 1], height[i]);
13.         }
14.                 //获取每个元素右边的最大值（从右到左遍历）
15.         vector<int> rightMax(n);
16.         rightMax[n - 1] = height[n - 1];
17.         for (int i = n - 2; i >= 0; --i) {
18.             rightMax[i] = max(rightMax[i + 1], height[i]);
19.         }
21.         int ans = 0;
22.         for (int i = 0; i < n; ++i) {
23.             ans += min(leftMax[i], rightMax[i]) - height[i];
24.         }
25.         return ans;
26.     }
27. };

复制代码

1. class Solution {
2. public:
3.     int trap(vector<int>& height) {
4.         int ans = 0;
5.         stack<int> stk;
6.         int n = height.size();
7.                 //遍历每一个元素
8.         for (int i = 0; i < n; ++i) {
9.                         //如果栈中有元素，且当前的柱子高于栈顶，既满足 left<=top<i
10.             while (!stk.empty() && height[i] > height[stk.top()]) {
11.                 int top = stk.top();
12.                 stk.pop();
13.                                 //防止栈中只有一个元素
14.                 if (stk.empty()) {
15.                     break;
16.                 }
17.                 int left = stk.top();
18.                 int currWidth = i - left - 1;
19.                 int currHeight = min(height[left], height[i]) - height[top];
20.                 ans += currWidth * currHeight;
21.             }
22.                         //i<=top 入栈
23.             stk.push(i);
24.         }
25.         return ans;
26.     }
27. };

复制代码

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 height 的长度。两个指针的移动总次数不超过 n。
  
• 空间复杂度：O(1)。只需要使用常数的额外空间。
  

对于官方题解的理解

[code]动态规划的做法中，需要维护两个数组 leftMax 和 rightMax，因此空间复杂度是 O(n)。是否可以将空间复杂度降到 O(1)？注意到下标 i 处能接的雨水量由 leftMax 和 rightMax 中的最小值决定。由于数组 leftMax 是从左往右计算，数组 rightMax 是从右往左计算，因此可以使用双指针和两个变量代替两个数组。维护两个指针 left 和 right，以及两个变量 leftMax 和 rightMax，初始时 left=0,right=n−1,leftMax=0,rightMax=0。指针 left 只会向右移动，指针 right 只会向左移动，在移动指针的过程中维护两个变量 leftMax 和 rightMax 的值。当两个指针没有相遇时，进行如下操作：使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值；如果 height[left]