首页 > 代码库 > Leetcode:Container With Most Water

Leetcode:Container With Most Water

题目大意是提供n个非负整数,a1,...,an,可以将其理解为多个边界(垂直的线段),其中ai处于x坐标i处,并且ai代表的线段高度即为ai的值。要求我们取这样的i与j,使得ai与aj以及x坐标轴围成的碗状物能容纳面积最多的水(即abs(i-j)*min(ai,aj)最大)。


最简单的方案就是暴力枚举:

res= -1, maxl = 0, maxr = 0

for(i=0; i < n; i++)

  for(j = i + 1; j < n; j++)

    res = max(abs(i-j)*min(a[i],a[j]), res)

说一下我的思路。假设函数maxCapacity({ai,...,aj})用于计算ai,...,aj中所能围成的碗状物的最大的保存水的容量,而函数capacity(ai,aj)=abs(i-j)*min(ai,aj)。

对于ai,...,aj,其中1<=i<j<=n:

若ai<aj,那么maxCapacity({ai,...,aj})=max(capacity(ai,aj), maxCapacity({ai+1,...,aj})

若ai>aj,那么maxCapacity({ai,...,aj})=max(capacity(ai,aj), maxCapacity({ai,...,aj-1})

若ai==aj,那么maxCapacity({ai,...,aj})=max(capacity(ai,aj), maxCapacity({ai+1,...,aj-1})

说明一下原因,如果ai和aj围成的碗状物的容量不是最大的,那么结果的边界必定不可能包含ai和aj中的较小值。这是因为对于最终的最优边界ab,ae(e>b),不妨假设ab=min(ai,aj),那么(e-b)*min(ab,ae)<=(e-b)*min(ai,aj)<(j-i)*min(ai,aj)=capacity(ai,aj)。这与ab和ae作为最优边界的定义相悖,因此结果的边界必定不可能包含ai和aj中的较小值。对于ai==aj的情况,ai和aj都可以作为较小值,因此ai和aj都不可能是最优边界之一。故最终的maxCapacity可以这样实现:

maxCapacity(a, i, j):

  if(i >= j)

    return 0

  if(ai < aj)

    sub = maxCapacity(a, i+1, j)

  else if(ai > aj)

    sub = maxCapacity(a, i, j-1)

  else

    sub = maxCapacity(a, i+1, j-1)

  return max((j - i) * min(a[i], a[j]), sub)

整段代码不算上的递归的部分的时间复杂度为O(1),而内部只发生一次递归且每次递归都必定将传入集合的大小减少1,而集合的初始大小为n,因此递归最多会发生n次,故总的时间复杂度为O(1)*n=O(n)。


最后老规矩,贴代码

技术分享
 1 package cn.dalt.leetcode;
 2 
 3 /**
 4  * Created by dalt on 2017/6/17.
 5  */
 6 public class ContainerWithMostWater {
 7     public int maxArea(int[] height) {
 8         return maxArea(height, 0, height.length - 1);
 9     }
10 
11     private int maxArea(int[] height, int i, int j) {
12         int sub;
13         if (j <= i) {
14             return 0;
15         } else if (height[i] < height[j]) {
16             sub = maxArea(height, i + 1, j);
17         } else if (height[i] > height[j]) {
18             sub = maxArea(height, i, j - 1);
19         } else {
20             sub = maxArea(height, i + 1, j - 1);
21         }
22         return Math.max((j - i) * Math.min(height[i], height[j]), sub);
23     }
24 }
View Code

 

Leetcode:Container With Most Water