LeetCode-Container With Most Water

Container With Most Water

##题目

####Container With Most Water

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.

##解题思路
该题是求解最大的容积问题，如果我们采用“暴力法”求解，则每一对pair都需要计算一次容积，然后获得最大的那个，时间复杂度为O(n^2)。
因此需要对其进行优化，这里我们可以采用左右夹逼法求解，从数组两端开始，分别设置左指针pLeft和右指针pRight,然后比较pLeft和pRight哪个数值大，假设pLeft小，则如果向左移动pRight,出现的容积不可能比现在好，因为瓶颈在pLeft处，所以只有向右移动pLeft,才可能出现更大的容积。当然，在这个左右移动指针的过程中，需要维护一个最大的容积。

##算法代码
代码采用JAVA实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
	//采用左右夹逼法
    public int maxArea(int[] height) {
        int len=height.length;
        if(len<=1) return 0;
        int maxarea=Integer.MIN_VALUE;
        int i=0;
        int j=len-1;
        while(i<j)
        {
        	int area=Math.abs(i-j)*Math.min(height[i],height[j]);
        	if(area>maxarea)
        		maxarea=area;
        	if(height[i]<height[j])
        		i++;
        	else
        		j--;
        }
        return maxarea;
    }
}

Comments

▲