当前位置：网站首页>11. Container With Most Water

11. Container With Most Water

2022-08-03 16:39:00 【51CTO】

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.

11. Container With Most Water_i++

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
      
1.
2.

       
       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;  
       
    }  
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.

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;
       
    }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.

       
       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
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.

       
       class Solution {
       
public:
       
    int maxArea(vector<int>& 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;
       
    }
       
};
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15740726/5540627

当前位置：网站首页>11. Container With Most Water

11. Container With Most Water

边栏推荐

猜你喜欢

随机推荐