No.011：Container With Most Water，no.011container

No.011：Container With Most Water，no.011container

題目：

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai).
n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).
Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

官方難度：

Medium

翻譯：

給定n個非負整數a1,a2,...,an，每一個數值代表坐標軸上的坐標(i,ai)。

n條垂直於橫坐標的豎線被畫出，用於連接點(i,ai)和(i,0)。

找到兩條線，與x軸一起形成一個容器，能夠容納最多的水。

注意：容器不能傾斜。

思路：

1.所謂容納最多的水的容器，言下之意就是容積V=x軸間距*MIN(線1，線2)。

2.最簡單的思想，用一個值記錄最大容積，兩次遍歷，將算出的容積值依次與最大容積比較，大則覆蓋，反之不動。

3.存在增加效率的方法。第一次正常遍歷，第二次遍歷可以取巧，使用反向遍歷。因為反向遍歷的情況下，x軸間距一定是越來越小的，使用一個變量記錄達到最高容積時的長度，之後遍歷到的長度只要低於記錄值，就可以不必計算容積直接略過，進入下一次遍歷。

解題中可能遇到的困難：

1.在使用優化的時候，注意將線2的最大長度的初始化工作放到內循環之外，因為每一次內循環結束後，長度需清0重新計算。

2.所謂的長度，是MIN(線1，線2)。

解題代碼：

1 private static int[] method(int[] array) { 2 int[] result = new int[2]; 3 int maxArea = 0; 4 for (int i = 0; i < array.length; i++) { 5 int maxHeight = 0; 6 // 第二次反向遍歷 7 for (int j = array.length - 1; j > i; j--) { 8 int height = Math.min(array[i], array[j]); 9 // 因為底越來越小，所以只有高度大於最高高度，才有比較面積的意義 10 if (height > maxHeight) { 11 // 不考慮面積比較結果，高先賦值 12 maxHeight = height; 13 if (height * (j - i) > maxArea) { 14 maxArea = height * (j - i); 15 result[0] = i; 16 result[1] = j; 17 } 18 } 19 } 20 } 21 return result; 22 } View Code

測試代碼地址：

https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/medium/Q011.java

LeetCode題目地址：

https://leetcode.com/problems/container-with-most-water/

PS：如有不正確或提高效率的方法，歡迎留言，謝謝！