leetcode.11---------Container With Most Water

标题:Given n non-negative integers a 1,a 2,..., 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軸に1,2,...,n点には垂直な線分が多く,長さはa 1,a 2,..., an.2つのセグメントを見つけて、彼らとxを囲む面積を最大にします.面積公式はMin(ai,aj)X|j-i|
方法1:暴力の窮挙方法

class Solution {
public:
	int maxArea(vector<int> &height)
	{
		int n = height.size();
		int max = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = i + 1; j < n; j++)
			{
				int temp = (j - i)*(height[i]>height[j] ? height[j] : height[i]);
				if (temp > max)
				{
					max = temp;
					continue;
				}
			}
		}
		return max;
	}
};

方法2:
The basic idea is simple: use two pointers to indicate the left edge and right edge of the water container. Every time move the lower edge towards another edge with one step. At last, we can find the max water container.

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

改善:

int maxArea(vector<int> &height) {
    int left = 0, right = height.size() - 1;
    int maxWater = 0;
    while(left < right){
        maxWater = max(maxWater, (right - left) * min(height[left], height[right]));
        height[left] < height[right] ? left++ : right--;
    }
    return maxWater;
}