feat: $42 增加双指针解法

lucifer · lucifer · commit cdb16aaa557d · 2020-06-29T16:01:12.000+08:00
diff --git a/problems/42.trapping-rain-water.md b/problems/42.trapping-rain-water.md
@@ -1,9 +1,9 @@
 ## 题目地址
+
 https://leetcode.com/problems/trapping-rain-water/description/
 
 ## 题目描述
 
-
 ```
 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
 
@@ -23,41 +23,48 @@ Output: 6
 
 ```
 
-## 思路
+## 前置知识
+
+- 空间换时间
+- 双指针
+- 单调栈
+
+## 双数组
+
+### 思路
 
 这是一道雨水收集的问题， 难度为`hard`. 如图所示，让我们求下过雨之后最多可以积攒多少的水。
 
-如果采用暴力求解的话，思路应该是height数组依次求和，然后相加。
+如果采用暴力求解的话，思路应该是 height 数组依次求和，然后相加。
 
 伪代码:
 
 ```js
-
-for(let i = 0; i < height.length; i++) {
-    area += (h[i] - height[i]) * 1; // h为下雨之后的水位
+for (let i = 0; i < height.length; i++) {
+  area += (h[i] - height[i]) * 1; // h为下雨之后的水位
 }
-
 ```
-问题转化为求h，那么h[i]又等于`左右两侧柱子的最大值中的较小值`，即
+
+问题转化为求 h，那么 h[i]又等于`左右两侧柱子的最大值中的较小值`，即
 `h[i] = Math.min(左边柱子最大值, 右边柱子最大值)`
 
-如上图那么h为 [0, 1, 1, 2, 2, 2 ,2, 3, 2, 2, 2, 1]
+如上图那么 h 为 [0, 1, 1, 2, 2, 2 ,2, 3, 2, 2, 2, 1]
 
 问题的关键在于求解`左边柱子最大值`和`右边柱子最大值`,
 我们其实可以用两个数组来表示`leftMax`, `rightMax`，
-以leftMax为例，leftMax[i]代表i的左侧柱子的最大值，因此我们维护两个数组即可。
-## 关键点解析
+以 leftMax 为例，leftMax[i]代表 i 的左侧柱子的最大值，因此我们维护两个数组即可。
+
+### 关键点解析
 
-- 建模 `h[i] = Math.min(左边柱子最大值, 右边柱子最大值)`(h为下雨之后的水位)
+- 建模 `h[i] = Math.min(左边柱子最大值, 右边柱子最大值)`(h 为下雨之后的水位)
 
-## 代码
+### 代码
 
-代码支持 JavaScript，Python3:
+代码支持 JavaScript，Python3，C++:
 
 JavaScript Code:
 
 ```js
-
 /*
  * @lc app=leetcode id=42 lang=javascript
  *
@@ -68,29 +75,28 @@ JavaScript Code:
  * @param {number[]} height
  * @return {number}
  */
-var trap = function(height) {
-    let max = 0;
-    let volumn = 0;
-    const leftMax = [];
-    const rightMax = [];
-
-    for(let i = 0; i < height.length; i++) {
-        leftMax[i] = max = Math.max(height[i], max);
-    }
+var trap = function (height) {
+  let max = 0;
+  let volumn = 0;
+  const leftMax = [];
+  const rightMax = [];
 
-    max = 0;
+  for (let i = 0; i < height.length; i++) {
+    leftMax[i] = max = Math.max(height[i], max);
+  }
 
-    for(let i = height.length - 1; i >= 0; i--) {
-        rightMax[i] = max = Math.max(height[i], max);
-    }
+  max = 0;
 
-    for(let i = 0; i < height.length; i++) {
-        volumn = volumn +  Math.min(leftMax[i], rightMax[i]) - height[i]
-    }
+  for (let i = height.length - 1; i >= 0; i--) {
+    rightMax[i] = max = Math.max(height[i], max);
+  }
 
-    return volumn;
-};
+  for (let i = 0; i < height.length; i++) {
+    volumn = volumn + Math.min(leftMax[i], rightMax[i]) - height[i];
+  }
 
+  return volumn;
+};
 ```
 
 Python Code:
@@ -107,9 +113,130 @@ class Solution:
             r[i] = max(r[i + 1], heights[i])
         for i in range(len(heights)):
             ans += max(0, min(l[i + 1], r[i]) - heights[i])
-        return ans     
+        return ans
 ```
 
+C++ Code:
+
+```c++
+int trap(vector<int>& heights)
+{
+	if(heights == null)
+		return 0;
+    int ans = 0;
+    int size = heights.size();
+    vector<int> left_max(size), right_max(size);
+    left_max[0] = heights[0];
+    for (int i = 1; i < size; i++) {
+        left_max[i] = max(heights[i], left_max[i - 1]);
+    }
+    right_max[size - 1] = heights[size - 1];
+    for (int i = size - 2; i >= 0; i--) {
+        right_max[i] = max(heights[i], right_max[i + 1]);
+    }
+    for (int i = 1; i < size - 1; i++) {
+        ans += min(left_max[i], right_max[i]) - heights[i];
+    }
+    return ans;
+}
+
+```
+
+**复杂度分析**
+
+- 时间复杂度：$O(N)$
+- 空间复杂度：$O(N)$
+
+## 双指针
+
+### 思路
+
+上面代码比较好理解，但是需要额外的 \${N} 的空间。从上面解法可以看出，我们实际上只关心左右两侧较小的那一个，并不需要两者都计算出来。具体来说：
+
+- 如果 l[i + 1] < r[i] 那么 最终积水的高度由 i 的左侧最大值决定。
+- 如果 l[i + 1] >= r[i] 那么 最终积水的高度由 i 的右侧最大值决定。
+
+因此我们不必维护完整的两个数组，而是可以只进行一次遍历，同时维护左侧最大值和右侧最大值，使用常数变量完成即可。这是一个典型的双指针问题，
+
+具体算法：
+
+1. 维护两个指针 left 和 right，分别指向头尾。
+2. 初始化左侧和右侧最低的高度都为 0。
+3. 比较 height[left] 和 height[right]
+
+   - 3.1 如果 height[left] < height[right]
+     - 3.1.1 如果 height[left] >= left_max， 则当前格子积水面积为(left_max - height[left])
+     - 3.1.2 否则无法积水，即积水面积为 0
+   - 3.2 左指针右移一位
+
+   - 3.3 如果 height[left] >= height[right]
+     - 3.3.1 如果 height[right] >= right_max， 则当前格子积水面积为(right_max - height[right])
+     - 3.3.2 否则无法积水，即积水面积为 0
+   - 3.4 右指针左移一位
+
+### 代码
+
+代码支持 Python3，C++:
+
+```python
+class Solution:
+    def trap(self, heights: List[int]) -> int:
+        n = len(heights)
+        l_max = r_max = 0
+        l, r = 0, n - 1
+        ans = 0
+        while l < r:
+            if heights[l] < heights[r]:
+                if heights[l] < l_max:
+                    ans += l_max - heights[l]
+                else:
+                    l_max = heights[l]
+                l += 1
+            else:
+                if heights[r] < r_max:
+                    ans += r_max - heights[r]
+                else:
+                    r_max = heights[r]
+                r -= 1
+        return ans
+```
+
+```c++
+
+class Solution {
+public:
+    int trap(vector<int>& heights)
+{
+    int left = 0, right = heights.size() - 1;
+    int ans = 0;
+    int left_max = 0, right_max = 0;
+    while (left < right) {
+        if (heights[left] < heights[right]) {
+            heights[left] >= left_max ? (left_max = heights[left]) : ans += (left_max - heights[left]);
+            ++left;
+        }
+        else {
+            heights[right] >= right_max ? (right_max = heights[right]) : ans += (right_max - heights[right]);
+            --right;
+        }
+    }
+    return ans;
+}
+
+};
+```
+
+**复杂度分析**
+
+- 时间复杂度：$O(N)$
+- 空间复杂度：$O(1)$
+
 ## 相关题目
 
 - [84.largest-rectangle-in-histogram](https://github.com/azl397985856/leetcode/blob/master/problems/84.largest-rectangle-in-histogram.md)
+
+更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 30K star 啦。
+
+关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
+
+![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
diff --git a/thinkings/binary-tree-traversal.md b/thinkings/binary-tree-traversal.md
@@ -20,6 +20,8 @@ DFS 图解：
 
 BFS 的关键点在于如何记录每一层次是否遍历完成， 我们可以用一个标识位来表式当前层的结束。
 
+首先不管是前中还是后序遍历，变的只是根节点的位置， 左右节点的顺序永远是先左后右。 比如前序遍历就是根在前面，即根左右。中序就是根在中间，即左根右。后序就是根在后面，即左右根。
+
 下面我们依次讲解：
 
 ## 前序遍历
