Container With Most Water

Jack-Cherish · Jack-Cherish · commit e78dcec6b3b8 · 2017-10-17T10:20:52.000+08:00
diff --git a/Array/Medium/11.Container With Most Water.md b/Array/Medium/11.Container With Most Water.md
@@ -0,0 +1,76 @@
+# 题目
+
+求最大水容器，给定一个包含正整数的数组，a1，a2，...，an。每个元素都可以呈现成一个点(i，ai)。过每个点，做垂直于x轴的垂线，得到对应交点(0，ai)。(0，ai)和(i，ai)构成一条之前。每条直线两两组合，构成一个储水容器，找到存储量最大的那个容器。
+
+**举例：**
+
+``` stylus
+Input：[1,3,5]
+(0,1) -> (1,1)
+(0,3) -> (2,3)
+(0,5) -> (3,5)
+Output：3
+```
+
+输入是[1,3,5]，那么一共有三条垂直与x轴的直线，直线两两组合，面积最大为3。
+
+# 思路
+
+最大盛水量取决于两边中较短的那条边，而且如果将较短的边换为更短边的话，盛水量只会变少。所以我们可以用两个头尾指针，计算出当前最大的盛水量后，将较短的边向中间移，因为我们想看看能不能把较短的边换长一点。这样一直计算到左边大于右边为止就行了
+
+# 代码
+
+**Python：**
+
+``` python
+class Solution(object):
+    def maxArea(self, height):
+        """
+        :type height: List[int]
+        :rtype: int
+        """
+        area_tmp = 0
+        area_max = 0
+        left = 0
+        right = len(height) - 1
+        while(left < right):
+            min_height = min(height[left], height[right])
+            area_tmp = (right - left) * min_height
+            if area_tmp > area_max:
+                area_max = area_tmp
+            if height[left] < height[right]:
+                left += 1
+            else:
+                right -= 1
+        return area_max
+```
+
+**C++：**
+
+``` cpp
+class Solution {
+public:
+    int maxArea(vector<int>& height) {
+        int left = 0;
+        int right = height.size() - 1;
+        int area_tmp = 0;
+        int area_max = 0;
+        while (left < right) {
+            area_tmp = (right - left) * (height[left] < height[right] ? height[left] : height[right]);
+            if (area_tmp > area_max) {
+                area_max = area_tmp;
+            }
+            if (height[left] < height[right]) {
+                left++;
+            }
+            else {
+                right--;
+            }
+        }
+        return area_max;
+    }
+};
+```
+
+
+
