feat(translation): Translate p42 and add cpp solution code (azl397985856#391)

EvelynL09 · web-flow · commit 404953b6e5c3 · 2020-06-16T10:09:55.000+08:00
diff --git a/README.en.md b/README.en.md
@@ -235,7 +235,7 @@ The data structures mainly include:
 - [0023.merge-k-sorted-lists](./problems/23.merge-k-sorted-lists.md)
 - [0025.reverse-nodes-in-k-group](./problems/25.reverse-nodes-in-k-groups-en.md) 🆕✅
 - [0032.longest-valid-parentheses](./problems/32.longest-valid-parentheses.md) 🆕
-- [0042.trapping-rain-water](./problems/42.trapping-rain-water.md)
+- [0042.trapping-rain-water](./problems/42.trapping-rain-water.en.md)🆕✅
 - [0052.N-Queens-II](./problems/52.N-Queens-II.md) 🆕
 - [0124.binary-tree-maximum-path-sum](./problems/124.binary-tree-maximum-path-sum.md)
 - [0128.longest-consecutive-sequence](./problems/128.longest-consecutive-sequence.md)
diff --git a/problems/42.trapping-rain-water.en.md b/problems/42.trapping-rain-water.en.md
@@ -0,0 +1,130 @@
+## Trapping Rain Water
+https://leetcode.com/problems/trapping-rain-water/description/
+
+## Problem 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.
+
+![42.trapping-rain-water-1](../assets/problems/42.trapping-rain-water-1.png)
+
+> The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
+
+```
+Input: [0,1,0,2,1,0,1,3,2,1,2,1]
+Output: 6
+```
+
+## Solution
+
+The difficulty of this problem is `hard`.
+We'd like to compute how much water a given elevation map can trap.
+
+A brute force solution would be adding up the maximum level of water that each element of the map can trap.
+
+Pseudo Code:
+```js
+for(let i = 0; i < height.length; i++) {
+    area += h[i] - height[i]; // the maximum level of water that the element i can trap
+}
+```
+
+Now the problem becomes how to calculating h[i], which is in fact the minimum of maximum height of bars on both sides minus height[i]:
+`h[i] = Math.min(leftMax, rightMax)` where `leftMax = Math.max(leftMax[i-1], height[i])` and `rightMax = Math.max(rightMax[i+1], height[i])`.
+
+For the given example, h would be [0, 1, 1, 2, 2, 2 ,2, 3, 2, 2, 2, 1].
+
+The key is to calculate `leftMax` and `rightMax`.
+
+## Key Points
+
+- Figure out the modeling of `h[i] = Math.min(leftMax, rightMax)`
+
+## Code (JavaScript/Python3/C++)
+
+JavaScript Code:
+
+```js
+
+/*
+ * @lc app=leetcode id=42 lang=javascript
+ *
+ * [42] Trapping Rain Water
+ *
+ */
+/**
+ * @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);
+    }
+
+    max = 0;
+
+    for(let i = height.length - 1; i >= 0; i--) {
+        rightMax[i] = max = Math.max(height[i], max);
+    }
+
+    for(let i = 0; i < height.length; i++) {
+        volumn = volumn +  Math.min(leftMax[i], rightMax[i]) - height[i]
+    }
+
+    return volumn;
+};
+
+```
+
+Python Code:
+
+```python
+class Solution:
+    def trap(self, heights: List[int]) -> int:
+        n = len(heights)
+        l, r = [0] * (n + 1), [0] * (n + 1)
+        ans = 0
+        for i in range(1, len(heights) + 1):
+            l[i] = max(l[i - 1], heights[i - 1])
+        for i in range(len(heights) - 1, 0, -1):
+            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     
+```
+
+C++ code:
+
+```c++
+class Solution {
+public:
+    int trap(vector<int>& height) {
+        //check for empty input array
+        if(height.empty())
+            return 0;
+        int size = height.size();
+        int leftMax[size], rightMax[size];
+        //initialization
+        leftMax[0] = height[0];
+        rightMax[size - 1] = height[size - 1];
+        //find leftMax for each element i
+        for(int i = 1; i < size; ++i)
+            leftMax[i] = max(leftMax[i-1], height[i]);
+        //find rightMax for each element i
+        for(int i = size - 2; i >= 0; --i)
+            rightMax[i] = max(rightMax[i+1], height[i]);
+        //caculating the result
+        int ans = 0;
+        for(int i = 0; i < size; ++i)
+            ans += min(leftMax[i], rightMax[i]) - height[i];
+        return ans;
+    }
+};
+```
+
+## Similar Problems
+
+- [84.largest-rectangle-in-histogram](https://github.com/azl397985856/leetcode/blob/master/problems/84.largest-rectangle-in-histogram.md)
