leetcode第11題：盛最多水的容器

二次循環

這道題比較容易想到的就是通過二次循環遍歷所有能盛的水的體積。

代碼

class Solution {public int maxArea(int[] height) {// 記錄最大體積int max = 0;// 左側for(int i=0;i<height.length;i++){// 右側for(int j =i+1;j<height.length;j++){// 計算體積int volumn = (j-i)*Math.min(height[i],height[j]);// 比較體積與當前最大值if(volumn>max)max = volumn;}    }return max;}
}

但是很明顯，當前這種方案的時間復雜度為O(n*n)，會在提交時超出時間限制。

雙指針優化

解析

那么嘗試進行優化，尋找這種情形下有沒有什么特點可以被發現。

這里可以觀察體積計算的公式
v = height*width，
(其中width=right-left; height=min(heights[right],heights[left]))的特性。

假設我們通過雙指針從height數組左右兩側依次向中間夾，那么width就會一直減小。而此時，我們只有讓水桶的木板變高才會讓容器的體積增大（一個變量始終減小或者增大，只需要考慮另一個變量就可以）。
因此在移動過程中，如果移動較高的那么體積必然減小，只有移動較低的才會可能讓體積增大（決定木桶體積的是最短板，而不是最長板）。
我們在遍歷的過程中不斷移動較短的部分，即：

if(height[left]>height[right]){right--;
}else{left++;
}

同時不斷計算當前移動后是不是大于記錄的最大容量，如果大于那么更新最大容量。

int volumn = Math.min(height[right],height[left])*(right-left);
if(volumn>max)max = volumn;

因此本道題目關鍵：

1.決定木桶體積的是最短板，而不是最長板
2.兩個變量計算的時候，如果控制其中一個始終減小或者增加，那么只需要關注另一個變量就可以
3.如果兩個變量增加減小無法控制，那么時間復雜度只能提高。

代碼

class Solution {public int maxArea(int[] height) {if(height.length==1)return 0;int left = 0;int right = height.length-1;int max = Math.min(height[left],height[right])*(right-left);// 左右依次遍歷// 移動較小的那根while(left<right){if(height[left]>height[right]){right--;}else{left++;}int volumn = Math.min(height[right],height[left])*(right-left);if(volumn>max)max = volumn;}return max;}
}