LeetCode Q11: 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.

• Mehtod1

Most naive way, two loops .

• Method2

	recursive dp version
	class Solution {
	public:
	int helper(vector<int>& height, int s, int e, vector<vector<int> >& dp) {
	if(s==e){
	dp[s][e]=0;
	return 0;
	}
	int r0=dp[s+1][e]!=-1? dp[s+1][e] : helper(height, s+1, e, dp);
	int r1=dp[s][e-1]!=-1? dp[s][e-1] : helper(height, s, e-1, dp);
	int r2=min(height[s], height[e])*(e-s);
	dp[s][e]=max(r0, max(r1, r2));
	return dp[s][e];
	}
	int maxArea(vector<int>& height) {
	vector<vector<int> > dp(height.size(), vector<int>(height.size(), -1));
	return helper(height, 0, height.size()-1, dp);
	}
	};

view raw q11ContainerMostWater2 hosted with ❤ by GitHub

• Method3

O(n) time method, use two pointers to scan the array once.
Suppose two points are s, e. In the beginning, s at the left end, e at the right end. The goal is to maximize the area. So, in this case, we always try to move the shortest bar between s and e to left(s) or to right(e) to look for next bigger area.

	class Solution {
	public:
	int maxArea(vector<int>& height)
	{
	int s=0;
	int e=height.size()-1;
	int maxarea=min(height[s], height[e]) * (e-s);
	while(s!=e)
	{
	if(height[s]<=height[e]){
	s++;
	}
	else{
	e--;
	}
	int tmp=min(height[s], height[e])*(e-s);
	if(tmp>maxarea){
	maxarea=tmp;
	}
	}
	return maxarea;
	}
	};

view raw Q11ContainerMostWater hosted with ❤ by GitHub