11. Container With Most Water

11. 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 and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

Input: [1,8,6,2,5,4,8,3,7]Output: 49

public class Solution { public int maxArea(int[] height) { int lpoint = 0, rpoint = height.length - 1; int area = 0; while (lpoint < rpoint) { area = Math.max(area, Math.min(height[lpoint], height[rpoint]) * (rpoint - lpoint)); if (height[lpoint] > height[rpoint]) rpoint--; else lpoint++; } return area; } }

Java

class Solution { public int maxArea(int[] height) { int l = 0; int r = height.length - 1; // idx values left and right int le = height[l]; int re = height[r]; // element value for left and right int thisLe = 0; int thisRe = 0; // for comparisons with previous elements int max = Math.min(le, re) * (r - l); // initial max area while(l < r) { le = height[l]; // left elemnt re = height[r]; // right element if (le < re) { thisLe = le; // for comparing it with next elements // find next elemnt towards right that is greater than this left element while (l < r && thisLe >= height[l]) l++; // finf max area max = Math.max(max, Math.min(height[l], height[r]) * (r - l)); } else if (le > re) { thisRe = re; // for comparing it with next elements // find next elemnt towards left that is greater than this right element while(l < r && thisRe >= height[r]) r--; // find area max = Math.max(max, Math.min(height[l], height[r]) * (r - l)); } else { // if both elements are same // calc area for them // and consider for elements towards each other max = Math.max(max, Math.min(height[l], height[r]) * (r - l)); l++; r--; // find max area for this new elements max = Math.max(max, Math.min(height[l], height[r]) * (r - l)); } } return max; }}

class Solution: def maxArea(self, height: List[int]) -> int: i = 0 j = len(height) - 1 max_area = 0 while i < j: m = height[i] if height[i] < height[j] else height[j] m = m * (j-i) max_area = max_area if max_area > m else m if height[j] > height[i]: i+=1 else: j-=1 return max_area

class Solution {public: int maxArea(vector& height) { int i = 0; int j = height.size() - 1; int max = -1; int area = 0; int h = 0; while (i < j) { if (height[i] < height[j]) h = height[i]; else h = height[j]; area = (j - i) * h; if (max < area) max = area; if (height[i] < height[j]) i++; else j--; } return max; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。