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.
给出 n 个非负整数 a1, a2, ..., an, 每个数字代表一个坐标(i, ai). 这些点分别垂直投影在 x 轴上并构成如 (i, ai) 和 (i, 0) 的 n 条纵线. 任意两条纵线与横坐标都可以构成一个容器, 找出一个容量最大的容器.
Note: You may not slant the container and n is at least 2.
注意: 容器不能倾斜, n >= 2
Example 1:
|
1 2 3 |
Input: [1,8,6,2,5,4,8,3,7] Output: 49 |
解题
贪心. 构成最大的容器, 可以从两个方面考虑: 纵线, 横坐标. 纵线越长越好, 横坐标越宽越好. 最初计算时, 选择最边缘的两条纵线, 保证横轴的最大利用, 之后, 由于容量取决于木桶最短板, 故左右两挡板最短的那个是瓶颈, 找到最短的一侧, 让其向里靠拢.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public: int maxArea(vector<int>& height) { int len = height.size(); int maxVolme = 0; int pointLeft = 0; int pointRight = len - 1; while(pointLeft < pointRight) { int BarrelEffect = (height[pointLeft] < height[pointRight]) ? height[pointLeft] : height[pointRight]; int temp = (pointRight - pointLeft) * BarrelEffect; maxVolme = temp > maxVolme ? temp : maxVolme; if (height[pointLeft] < height[pointRight]) { pointLeft++; } else { pointRight--; } } return maxVolme; } }; |
via: https://leetcode.com/problems/container-with-most-water/
