C#解leetcode 11. Container With Most Water

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.

由于这个题的题意十分不清楚，有必要解释一下：这可以理解为在一个二维坐标系下面，求两条与x垂直的直线 和 x轴 围成的  图形的面积最大值。

 

在讨论区看到了一个解法非常巧妙的回答，姑且摘录如下。如要更好的理解这个算法的思想，有必要看看下面的解释说明：

首先假设有一个6*6的矩阵，如图。在图中x的部分代表不用计算的情况，之所以不用计算是因为：

（1）对角线上两个元素相等

（2）左下三角和右上三角式对称的，只需要计算其中之一就行，我们选择右上三角进行计算

我们首先计算（1,6）点（可以理解为取第一条直线和第二条直线），标记为o。如果左侧的直线小于右侧的直线，则（1,2），（1,3），（1,4），（1,5）的值都会比（1,6）要小（因为计算面积的时候取得是两条直线中的较小值，所以其余的组合一定小于（1,6）），因此，其余的组合都可以不用在计算了。不用计算的点用---表示。

然后我们移动到了(2,6)点（也就是选择第二条直线和第六条直线）,此时，如果右侧的直线小于左侧的直线，则（3,6），（4,6），（5,6）又可以不用计算了

按照上面的规律，我们不论o最终移动到什么地方，我们仅仅需要进行n-1次判断就可以得到结果

 

下面贴上用C#语言的实现过程：

public class Solution {
    public int MaxArea(int[] height) {
        
        int max=0,Area=0,i=0,j=height.Length-1;
        
       while(i!=j)
       {
           if(height[i]<height[j])
           {
              Area= height[i]*(j-i);
              i++;
           }
           else
           {
               Area= height[j]*(j-i);
               j--;
           }
          max=Math.Max(max,Area);
       }
        
        return max;
    }
}