LeetCode -- Container With Most Water

LeetCode -- 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.


已知一個height數組，代表從0到n的縱坐標，對於height[i]和height[j]來說，它們構成的最大水容量為i和j的距離 * Min(height[i], height[j])。問，求出height數組中哪兩點間的水容量最大？


思路：
算是一個two pointer的經典問題，左右兩邊開始找,left=0,right = n-1：
1. 如果左邊高度低，則left++；如果右邊高度低，則r--；如果相等，則left++並且right--;
2. 每次計算左右兩點的水容量，並更新max值即可




實現代碼：

public class Solution {
    public int MaxArea(int[] height) {
        var l = 0;
    	var r = height.Length - 1;
    	var max = 0;
    	while(l < r){
    		var current = Math.Min(height[l], height[r]) * (r - l);
		    max = Math.Max(max , current);
		    
    		if(height[l] < height[r]){
    			l++;
    		}
    		else if(height[l] > height[r]){
    			r--;
    		}
    		else{
    			l++;
    			r--;
    		}
    	}
    	return max;
    }
}