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.
Solution 1：Sort points by height, then from low to heigth, find the max difference of x-axises which is higher than current, to do this efficiently, remove edges lower or equal to current height.
class Solution { class p { int x,y; p(int a, int b) { x = a; y = b; } } public int maxArea(int[] height) { int len = height.length; p[] ps = new p[len]; for (int i = 0; i < len; i++) { ps[i] = new p(i+1,height[i]); } Arrays.sort(ps,new Comparator<p>() { @Override public int compare(p o1, p o2) { return o1.y - o2.y; } }); int max = 0; int leftMax = 0, rightMax = len-1; for (int i = 0; i < len-1; i++) { int maxl = 0; max = Math.max(max,Math.max(ps[i].x-1-leftMax,rightMax+1-ps[i].x)*ps[i].y); while (leftMax < rightMax && height[leftMax] <= ps[i].y) { leftMax++; } while (rightMax > leftMax && height[rightMax] <= ps[i].y) { rightMax--; } } return max; } }
Container With Most Water--排序后递减长度
原文：https://www.cnblogs.com/liudebo/p/9309162.html