11.盛最多水的容器

算法思路

此類問題用雙指針法，效率最高。雙指針，顧名思義就是使用兩個指針變量，分别初始化為開始位置和末尾位置，在條件适合時，i++或j–;直到i和j相等，循環結束。

矩陣的面積與兩個因素有關：

矩陣的長度：兩條垂直線的距離

矩陣的寬度：兩條垂直線其中較短一條的長度

是以，要矩陣面積最大化，兩條垂直線的距離越遠越好，兩條垂直線的最短長度也要越長越好。

設定兩個指針 left 和 right，分别指向數組的最左端和最右端。此時，兩條垂直線的距離是最遠的，若要下一個矩陣面積比目前面積來得大，必須要把 height[left] 和 height[right] 中較短的垂直線往中間移動，看看是否可以找到更長的垂直線。若位置left的值小于位置right的值，left加1，否則right減1，每次求得maxarea = max(maxarea,(j-i)*max(height[i],height[j]))，直到left<right循環結束。

代碼

class Solution {
    public int maxArea(int[] height)
    {
        /*雙指針法 left左指針，right右指針，
        當left<right時，若位置left的值小于位置right的值，left加1，否則right減1，
        每次求得maxarea = max(maxarea,(j-i)*max(height[i],height[j]))
        */
        int left = 0,right = height.length-1,maxarea = 0;
        while(left<right){
            maxarea = Math.max(maxarea,(right-left)*Math.min(height[left],height[right]));                  
            if(height[left] <= height[right]) left++;
            else right--;
        }
        return maxarea;
        /*
        int i=0,j=height.length-1,maxarea = 0;
        while(i!=j)
        {
            int high = height[i]>=height[j] ? height[j] : height[i];
            maxarea = maxarea >= ((j-i)*high) ? maxarea : (j-i)*high;
            if(height[i] >= height[j])
                j--;
            else
                i++;
        }
        return maxarea;      
        */ 
    }
}
           

複雜度

時間複雜度：O(N)，隻進行了一趟周遊

空間複雜度：O(1)，沒有額外開辟空間