Container With Most Water（容器装更多的水）

发表于 | 更新于: | 分类于 ， | | 阅读次数: |
字数统计: 205 | 阅读时长 ≈ 1

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.

C解法：

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
int maxArea(int* height, int heightSize) {
    int maxarea = 0;
    int l = 0;
    int r = heightSize - 1;
    
    while(l < r) 
    {
        int minPlate = height[l];
        if(height[l] > height[r]) 
        {
            minPlate = height[r]; 
        }
        int area = (r -l) * minPlate;
        if(area > maxarea) {
            maxarea = area;
        }
        if(height[l] < height[r]) 
        {
            l++;
        }
        else 
        {
            r--;
        }
    }
    return maxarea;
}

C++解法：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0, i = 0, j = height.size() - 1;
        while (i < j) {
            res = max(res, min(height[i], height[j]) * (j - i));
            height[i] < height[j] ? ++i : --j;
        }
        return res;
    }
}

(全文完)