【Leetcode】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.

 1 class Solution {
 2 public:
 3     int maxArea(vector<int> &height) {
 4         int i = 0, j = height.size() - 1;
 5         int max_area = 0;
 6         while (i < j) {
 7             int area = (j - i) * min(height[j], height[i]);
 8             if (area > max_area) {
 9                 max_area = area;
10             }
11             if (height[i] <= height[j]) {
12                 ++i;
13             } else {
14                 --j;
15             }
16         }
17         return max_area;
18     }
19 };

View Code

容器的容积 C = min(ai, aj) * (j - i) (这里令 j > i) 。

从两边向中间夹逼扫描，所以第一个计算的是 j = n - 1, i = 0;

那么在夹逼的过程中，什么时候应该左指针向右，什么时候右指针向左呢？

回到容积计算公式，两边向中间扫描的过程中，因式中的(j - i)项一定是变小了，所以只有min(ai, aj)项增大才可能使得容积变大。所以应该当ai小的时候，右移左指针，aj小的时候左移右指针，检查下一个可能使得容积变大的容器。