[LeetCode] Container With Most Water

1994 ワード

Container With Most Water Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not slant the container.
問題解決の考え方:
この問題の意味は直角平面にx軸に垂直なn本の線があり、隣接する線は1から離れており、2本の線を選択し、x軸と容器を構成している.このような容器を求めて最大でどれだけの水を詰めることができますか?
1、基本的な方法、2つの組み合わせで、最大値を計算します.時間的複雑度はO(n^2)である.タイムアウトエラーが発生しました.
class Solution {
public:
    int maxArea(vector<int>& height) {
        //naiv  
        int len = height.size();
        if(len<2){  //                
            return 0;
        }
        int maxArea=0;
        int minHeight = 0;
        for(int i=1; i<len; i++){
            minHeight = height[i];
            for(int j=i-1; j>=0; j--){
                minHeight = min(height[i], minHeight);
                if(minHeight==0){
                    break;
                }
                maxArea=max(maxArea, minHeight*(i-j));
            }
        }
        return maxArea;
    }
    
    int min(int a, int b){
        return a>b?b:a;
    }
    
    int max(int a, int b){
        return a>b?a:b;
    }
};
2、talentの方法を比較して、両側を挟んで、左の板が右より小さい場合は、左の板を移動して、さもなくば右の板を移動します.これだけ容量が大きくなる可能性があるからです.
class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        int len = height.size();
        int i=0, j=len-1;
        while(i<j){
            maxArea=max(maxArea, min(height[i], height[j])*(j-i));
            if(height[i]<height[j]){
                i++;
            }else{
                j--;
            }
        }
        
        return maxArea;
    }
    
    int max(int a, int b){
        return a>b?a:b;
    }
    
    int min(int a, int b){
        return a>b?b:a;
    }
};