leetcode:Container With Most Water

leetcode:Container With Most Water

題目

給定一系列整數代表在0,1,2,3...坐標點板的高度,求出在任意兩個板之間能裝水的最大截面積.

分析

首先,我們會想到遍歷下每一個板,選取任意兩個板,求出最大的,但是這個會超時,效率太低

其次,我們樂意想到在遍歷的基礎上優化,即有一個預測,這樣可以在一定程度上提高效率,但是並不是太好,我試了下還




是不能過.

我們就要想,能不能遍歷一遍就求出來.

1:left = 0, right =height.size();

2:如果left< right,則3,否則四

3:求出此時面積的大小,並判斷左邊和右邊板的高度哪一個大,左邊小於右邊的話,left++;否則,right--;並判斷是否

將Maxarea更新,返回2

4:結束,返回最大面積




窮舉

class Solution {
public:
    int maxArea(vector &height) {
        int area,Maxarea,high;
        Maxarea = 0;
        for(int i=0;iheight[j]? height[j]:height[i]);
        		if(area>Maxarea)
        			Maxarea = area;
        	}
        }
        return Maxarea;
    }
};

預測優化

class Solution {
public:
    int maxArea(vector &height) {
        int area,Maxarea,high;
        Maxarea = 0;
        for(int i=0;iheight[j]? height[j]:height[i]);
        		if(area>Maxarea)
        			Maxarea = area;
        	}
        }
        return Maxarea;
    }
};


雙指針

class Solution {
public:
    int maxArea(vector &height) {
        int left = 0;
        int right = height.size() - 1;
        int area,Maxarea,high,step;
        Maxarea = 0;
        int flag;
        while(leftheight[right]? height[right]:height[left]);
        	if(height[left]Maxarea)
        		Maxarea = area;
        }
        return Maxarea;
    }
};