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:


贪心. 构成最大的容器, 可以从两个方面考虑: 纵线, 横坐标. 纵线越长越好, 横坐标越宽越好. 最初计算时, 选择最边缘的两条纵线, 保证横轴的最大利用, 之后, 由于容量取决于木桶最短板, 故左右两挡板最短的那个是瓶颈, 找到最短的一侧, 让其向里靠拢.

via: https://leetcode.com/problems/container-with-most-water/

Hello world!
文章已创建 200