11. Container With Most Water

題意

給定n個非負整數\(a_1,a_2,...,a_n\),其中每個數表示坐標點\((i,a_i)\),i是數組下標,\(a_i\)是對應高度.尋找兩條線,使得兩條線構成的長方形面積最大,盛水最多.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

解

暴力破解

對每種情況進行循環,計算對應的面積,同時保存最大的面積.

class Solution {
public:int maxArea(vector<int>& height) {if (height.size()<2)return 0;int res = 0;for(int i=0;i<height.size();i++){for(int j=i+1;j<height.size();j++){int minH = min(height[i], height[j]);res = max(res, minH*(j-i));}}return res;}
};

時間復雜度O(N*N).時間復雜度太高.而復雜度太高主要是進行了一些實際上并不需要的計算,盡管利用對稱性,減少了一半的計算量.

雙指針

思路:面積等于底*高,底是由兩條線下標差決定,高是由兩條線最短的線決定(木桶理論).假如有兩個指針left和right分別指向頭和尾,此時的面積是\(min(a[left],a[right])*(N-1)\),而且這時候的底是最長的.如果這時候的面積值并不是最大值,也就是說存在:

\(Base * Height > min(a_1,a_N) * (N-1)\).

這種情況下由于Base一定小于(N-1),也就是說Height要比之前的大,那么,應該一定\(a_1,a_N\)兩條線中較短的那條線,保證面積的高度可以發生改變(增大),也就是說:

• 如果\(a_1 < a_N\),問題變成在\(a_2,a_N\)之間查找最大面積,也就是left++;
• 如果\(a_1 > a_N\),問題變成在\(a_1,a_{N-1}\)之間查找最大面積,也就是right--;

class Solution {
public:int maxArea(vector<int>& height) {int left=0, right = height.size()-1;int area = 0;while(left < right){area = max(area, min(height[left], height[right])*(right-left));if(height[left] < height[right]) left++;else right--;}return area;}
};

時間復雜度O(N).

優化:關注自己解法存在的問題,優化方向是什么.比如說暴力破解方法,N*N,主要是因為做了一些不必要的計算,所以下一步的優化方向就是如何減少這些計算,這就需要重新審題,發現題目中的隱藏信息以及問題存在的性質.