lintcode：装最多水的容器

装最多水的容器

给定 n 个非负整数 a1, a2, ..., an, 每个数代表了坐标中的一个点 (i, ai)。画 n 条垂直线，使得 i 垂直线的两个端点分别为(i, ai)和(i, 0)。找到两条线，使得其与 x 轴共同构成一个容器，以容纳最多水。

解题

不理解题意

通俗的说

在上面n个点中找到两个点，使得线段一：(i,ai) (i,0), 线段二:(j,aj) (j,0) 线段三：(i, 0) (j, 0) 这三个线段能够组成的容器可以盛放最多的水

二分法，找到一个区间求出最大面积

 1 public class Solution {
 2     /**
 3      * @param heights: an array of integers
 4      * @return: an integer
 5      */
 6     public int maxArea(int[] A) {
 7         // write your code here
 8         if(A == null || A.length <2)
 9             return 0;
10         int Max = 0;
11         int left = 0;
12         int right = A.length -1;
13         int subMax = 0;
14         while(left < right){
15             if(A[left] < A[right]){
16                 subMax = (right - left)*A[left];
17                 left++;
18             }else{
19                 subMax = (right - left)*A[right];
20                 right--;
21             }
22             Max = Math.max(subMax,Max);
23         }
24         
25         return Max;
26     }
27 }

Java Code

 1 class Solution:
 2     # @param heights: a list of integers
 3     # @return: an integer
 4     def maxArea(self, A):
 5         # write your code here
 6         if A == None or len(A)<2:
 7             return 0
 8         Max = 0
 9         subMax = 0
10         low = 0
11         high = len(A) - 1
12         while low< high:
13             if A[low] <A[high]:
14                 subMax = (high - low)*A[low]
15                 low+=1
16             else:
17                 subMax = (high - low)*A[high]
18                 high-=1
19             Max = max(Max,subMax)
20         return Max 
21 
22

Python Code