LeetCode盛最多水的容器

題目描述

看到這題，顯然像我這種菜雞首先想到的當然是暴力法

int maxArea(vector<int>& height) {
    int len = height.size();
    int area = INT_MIN;
    for(int i=0; i<len-1; i++){
        for(int j=i+1; j<len; j++){
            int temp = (height[i]<height[j]? height[i] : height[j]) * (j-i);
            area = temp > area? temp : area;
        }
    }
    return area;
}      

雖然結果正确，顯然效率低下，我還以為肯定會逾時，沒想到居然過了

慘不忍睹，并不想多說什麼。于是開始向網友尋求更高效的解法，有了下面的第二版(雙指針)

int maxArea(vector<int>& height) {
    int area = INT_MIN;
    int low = 0;
    int high = height.size()-1;
    while(low < high){
        int h = height[low]<height[high] ? height[low] : height[high];
        area = area > h*(high-low) ? area : h*(high-low);
        if(height[low]<height[high])  low++;
        else high--;
    }
    return area;
}