package code;

import java.util.Arrays;

public class Code11 {

	/*
	 * 对于这种类型的题目,所求解是ans=x&y同时决定,可以归纳为二元约束问题。
	 * 一般的解法,很明显是,先分解掉一个x约束,再由剩下的变量y,来找最优的解。
	 * 此题目意思是:在一个水平面上,有n根平行与y轴的线段,起点是[i,0],终点是[0,height[i]],
	 * 取其中的两条线段,能够容纳最多的水.
	 * 简化为 ans=max{(j-i)*min(height[i],height[j])},其中0=<i,j<n
	 * 
	 * 暴力解法枚举所有的(i,j)组合,标准的时间复杂度O(n*n),TLE
	 * 最关键的问题,我们不知道height[j]是否大于height[i],所以我们也没法选取j-i的最大值,来
	 * 得到最终ans的最大值
	 * 那么我们可以保留每个(height[i],i),根据height排序
	 * 选取height[j]>=height[i], 再选取Min[index[i+1,n]],或Max[index[i+1,n]],
	 * 最后可以推导出最优的解。
	 * 具体细节,还需要自己想清楚
	 */
	class dual implements Comparable<dual>{
		int val;
		int idx;
		
		public dual(int a,int b){
			val=a;
			idx=b;
		}
		@Override
		public int compareTo(dual o) {
			// TODO Auto-generated method stub
			return val-o.val;
		}
	}
 public int maxAreaII(int[] height) {
 	int ans=0;
 	int n=height.length;
 	dual[] list=new dual[n];
 	int i,j;
 	for(i=0;i<n;i++)
 		list[i]=new dual(height[i],i);
 	
 	Arrays.sort(list);
 	int[] maxIdx=new int[n];
 	int[] minIdx=new int[n];
 	for(i=n-1;i>=0;i--){
 		if(i==n-1){
 			maxIdx[i]=list[i].idx;
 			minIdx[i]=list[i].idx;
 		}
 		else{
 			maxIdx[i]=maxIdx[i+1]>list[i].idx?maxIdx[i+1]:list[i].idx;
 			minIdx[i]=minIdx[i+1]<list[i].idx?minIdx[i+1]:list[i].idx;
 		}
 	}
 	for(i=0;i<n-1;i++){
 		int a=Math.abs(list[i].idx-maxIdx[i+1]);
 		int b=Math.abs(list[i].idx-minIdx[i+1]);
 		a=a>b?a:b;
 		a*=list[i].val;
 		if(ans<a)
 			ans=a;
 	}
 	return ans;
 }
 /*
 * 其实官方版的,效率更高O(n)
 * 贪心
 * 先想象一下,什么时候,最有可能出现最优解,就是我先选0与n-1的两个元素
 * 然后,将两块隔板往内部移动,短的板子被往里移动,最后所得到的解为最优解
 */
 public int maxArea(int[] height) {
 	int ans=0;
 	int n=height.length;
 	int left=0,right=n-1;
 	while(left<right){
 		int temp=height[left]<height[right]?height[left]:height[right];
 		temp*=(right-left);
 		if(ans<temp)
 			ans=temp;
 		if(height[left]<height[right]){
 			left++;
 		}
 		else
 			right--;
 	}
 	return ans;
 }
 public static void main(String[] args){
 	int[] height={5,4,3,7,6};
 	new Code11().maxArea(height);
 }
	
}