[LeetCode] 11. Container With Most Water

轉自LeetCode

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.

<Solution>
這題要畫個圖，才會比較明白在問什麼

input : [1,1,3]

那最大的 container 就是 w x h = (2 - 0) * min(1,3) = 2

code 如下

C++

	class Solution {
	public:
	int maxArea(vector<int>& height) {
	int ans = 0;
	int left = 0, right = height.size() - 1;
	while(left < right) {
	ans = max(ans, min(height[left], height[right]) * (right - left));
	//> keep the max height
	if(height[left] < height[right]) {
	++left;
	}
	else {
	--right;
	}
	}
	return ans;
	}
	};

view raw containerWithMostWater.cpp hosted with ❤ by GitHub

Java

	public class Solution {
	public int maxArea(int[] height) {
	int ans = 0;
	int left = 0, right = height.length-1;
	while(left < right) {
	if(height[left] < height[right]) {
	ans = Math.max(ans, (right-left) * height[left]);
	++left;
	}
	else {
	ans = Math.max(ans, (right-left) * height[right]);
	--right;
	}
	}
	return ans;
	}
	}

view raw containerWithMostWater.java hosted with ❤ by GitHub