2019-10-08

乘更多的水

题目：
　给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
　说明：你不能倾斜容器，且 n 的值至少为 2。
　示例:
　输入: [1,8,6,2,5,4,8,3,7]
　输出: 49

解题思路：
此题意味着垂直的两条线段将会与坐标轴构成一个矩形区域，较短线段的长度将会作为矩形区域的宽度，两线间距将会作为矩形区域的长度，而我们必须最大化该矩形区域的面积，所以考虑面积最大的情况。
方法一：暴力法
代码(根据力扣官网提交作品的格式)：

public class Solution {
    public int mArea(int[] height) {
        int max=0; //存放最大值
        for (int i=0;i<height.length;i++)
            for (int j=i+1;j<height.length;j++)
                max = Math.max(max, Math.min(height[i], height[j])*(j-i)); //最大面积=较短边×下标的差
        return max;
    }
}

　复杂度分析：
　时间复杂度：O(n²)
　空间复杂度：O(1)

方法二：双指针法
思路：在方法一暴力求解的前提下，我们考虑两线段之间形成的区域总是会受到其中较短那条长度的限制。此外，两线段距离越远，得到的面积就越大。
　我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。此外，我们会使用变量 maxarea 来持续存储到目前为止所获得的最大面积。在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 maxarea，并将指向较短线段的指针向较长线段那端移动一步。
　为了使面积最大化，我们需要考虑更长的两条线段之间的区域。如果我们试图将指向较长线段的指针向内侧移动，矩形区域的面积将受限于较短的线段而不会获得任何增加。但是，在同样的条件下，移动指向较短线段的指针尽管造成了矩形宽度的减小，但却可能会有助于面积的增大。因为移动较短线段的指针会得到一条相对较长的线段，这可以克服由宽度减小而引起的面积减小。
代码(根据力扣官网提交作品的格式)：

public class Solution {
    public int maxArea(int[] height) {
        int maxarea = 0,i = 0, j = height.length - 1; //指针i和j分别指向首部和尾部
        while (i < j) { //i小于j才能循环
            maxarea = Math.max(maxarea, Math.min(height[i], height[j]) * (j - i)); //最大面积=较短边×下标的差
            if (height[i] < height[j]) //如果左边的值小，就将指针i右移
                i++;
            else     //如果右边的值小或者两者相等，就将指针j左移
                j--;
        }
        return maxarea;
    }
}

　复杂度分析：
　时间复杂度：O(n)
　空间复杂度：O(1)
完整代码

import java.util.Scanner;
public class Ji {
	public static void main(String[] args) {
		   Scanner input=new Scanner(System.in);
		   int n=input.nextInt();  //输入n个柱状
		   int[] a=new int[n];    //动态生成n大小的整型数组
		   for(int w=0;w<a.length;w++)
		   {
			   a[w]=input.nextInt();  //循环输入每个柱状的值
		   }   
		    System.out.println(maxArea(a));	  //输出最终值
		}	   
			
	public static  int maxArea(int[] height) {
	       int maxarea=0,i=0,j=height.length-1; //指针i和j分别指向首部和尾部
	       while(i<j)
	       {
	    	   maxarea=Math.max(maxarea,Math.min(height[i], height[j])*(j-i)); //最大面积=较短边×下标的差
	    	   if(height[i]<height[j])
	    		   i++;  //如果左边的值小，就将指针i右移
	    	   else
	    		   j--;  //如果右边的值小或者两者相等，就将指针j左移
	       }
	         return maxarea;
	 }
	
	
	
}