0x00 Problem
Description
Given \(n\) non-negative integers \(a_1, a_2, ..., a_n\) , where each represents a point at coordinate \((i, a_i)\). \(n\) vertical lines are drawn such that the two endpoints of the line \(i\) is at \((i, a_i)\) and \((i, 0)\). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant(倾斜) the container. 1
2
3Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 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.
0x01 Answer
本题标准解法为双指针法，时间复杂度为\(O(n)\)。
Solution
设置两个指针i和j，分别指向输入数组的头部和尾部。即i=0,j=len(arr)-1。
进行循环，每次循环过程将i往右移动或者将j往左移动，一轮循环只移动一个指针。当指针i与指针j相遇时，终止循环。
每次循环时计算当前指针指向位置所能容纳的最大水量，并保存该最大水量值。
移动i或者移动j由arr[i]和arr[j]的大小决定。若arr[i] < arr[j]，则将i向右移动，反之，则将j向左移动。i只会由左向右移动，j只会由右向左移动。表现上即i和j都在互相靠近，直到相遇。每次循环移动的指针为指向的值较小的指针。
Correctness
该解法的正确性的定性论证如下。假设指针i对应的数组值为\(f(i)\)
设对\(i,j\)有\(S(i,j)\)表示此时存储的水量。根据短板效应，此时的水量为\(S(i,j)=min(f(i),f(j)) * (j - i)\)
假设 \(f(i) < f(j)\)。
若移动\(i\)，则新的蓄水量\(S_1 = S(i+1,j) = min (f(i+1),f(j)) * (j-i-1)\)
- 若\(f(i+1) > f(j)\)，宽度减少，高度增加到\(f(j)\)，则有 \(S_1 > S(i,j)\) 或 \(S_1 <= S(i,j)\)。
若\(f(i+1) <= f(j)\)，宽度减少，高度依然有可能增加（\(f(i+1)>f(i)\)的情况)，有 \(S_1 < S(i,j)\)或 \(S_1 <= S(i,j)\)。
- 即移动\(i\)后，新的蓄水量可能变大或者变小。
- 若移动\(j\)，则新的蓄水量\(S_2 = S(i,j - 1) = min (f(i),f(j - 1)) * (j-i-1)\)
- 若\(f(i) > f(j - 1)\)，宽度减少，高度也减少。则有\(S_2 <= S(i,j)\)。
- 若\(f(i) <= f(j - 1)\)，宽度减少，高度不变（根据短板效应，高度为\(f(i)\)) 则有 \(S_2 < S(i,j)\)。
- 无论如何，移动\(j\)后，新的蓄水量一定变小。
故我们只移动i和j中指向的值较小的那个。