https://oj.leetcode.com/problems/container-with-most-water/
http://fisherlei.blogspot.com/2013/01/leetcode-container-with-most-water.html
public class Solution {
public int maxArea(int[] height) {
// Solution B:
// return maxArea_BruteForce(height);
// Solution A:
return maxArea_TwoPointer(height);
}
//////////////////////
// Solution A: Two Pointer
//
// O(n)
public int maxArea_TwoPointer(int[] height)
{
// 从两段向中间遍历
// 如果 left <= right, 寻找下一个比现在left更大的left
// 如果 left > right, 寻找下一个比现在right更大的right
int l = 0;
int r = height.length - 1;
int max = 0;
while (l < r)
{
int area = area(height, l, r);
max = Math.max(area, max);
if (height[l] <= height[r])
{
l ++;
}
else
{
r --;
}
}
return max;
}
////////////////
// Solution B: Brute Force
//
// O(n^2)
private int maxArea_BruteForce(int[] height)
{
if (height == null || height.length < 2)
return 0;
int max = -1;
int len = height.length;
for (int i = 0 ; i < len ; i ++)
{
for (int j = len - 1 ; j > i ; j --)
{
int area = area(height, i, j);
if (area > max)
max = area;
}
}
return max;
}
////////////////
// Tools:
private int area(int[] h, int i, int j)
{
return Math.abs(Math.min(h[i], h[j]) * (i - j));
}
}[LeetCode]11 Container With Most Water
原文：http://7371901.blog.51cto.com/7361901/1598408