題目要求
思路
1.正常用雙循環外循環i從0開始,內循環從height.size()-1開始去計算每一個值是可以的,但是因為數據量太大,會超時。
2.考慮到超時,需要優化一些,比如第一個選下標1,第二個選下標3和第一個選下標3,第二選擇下標1是一樣的,所以,內循環遍歷到小于
時,數據重復可以跳過,但是優化后還是超時
3.考慮優化高度,如果i一樣,height[j] > height[j-1],說明高度要么減小要么不變,但是由于底減少,所以面積肯定降低,所以再拿height[j] > height[j-2]進行比較,只要小于height[j]的都可以跳過。同理如果j一樣,height[i] > height[i+1]如果滿足這個,也可以跳過。但是優化后還有超時
4.此時說明雙循環已經不能滿足了,我們采用雙指針left和right,此時,底部已經是最大的了,我們可以將兩個值較小的那個往中間移動,去尋找更大面積的組合。
代碼實現
class Solution {
public:int maxArea(vector<int>& height) {int left = 0;int right = height.size() - 1;int s = 0;int max = 0;while(left < right){int h = min(height[left], height[right]);s = h * (right - left);if(s > max)max = s;//移動指針if(height[left] > height[right])right--;elseleft++;}return max;}
};