LeetCode 11.Container With Most

题目

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 and n is at least 2.

题目大意:
给定n个非负整数a1,a2,…,an,ai与x轴对应的i点相连形成n条垂直的直线,从这n条线中找出两条使得与x轴形成一个容器(且该容器盛水最多)

分析

这道题如果我们从任意一边遍历的话,势必要花费O(n^2)的时间来解决,效率太低。

我们现在换一种思路,既然要求容器的盛水量(即面积),影响面积大小的因素有两个长和高,我们分别从x轴的两端开始向中间查找,这样可以保证在O(n)时间内遍历完数组(但是,这样高度必然会不断减小),所以我们要不断的需找更高的垂直线来替补。

实现代码

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length-1;
int result = 0;
while (left != right){
result = Math.max(Math.min(height[left],height[right])*(right-left), result);
if (height[left] < height[right])
left ++;
else
right --;
}
return result;
}
}