题目描述：

给定一个长度为n的整数数组，表示n个垂直的线。在二维坐标系里面，第i个垂直的线的两端的坐标是(i,0)和(i, height[i])。

找到两条线，加上坐标系的水平坐标系，组成一个容器，假设我们可以用这个容器装水。

找到能够装的最大容量。

说明：不考虑容器倾斜的情况。

Example 1

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

Example 2

输入：height = [1,1]
输出：1

解题思路

首先，从height数组中，给定i，j两个位置的高度，面积通过高*宽计算，高是两个高度中的较小的数(木桶短板问题，容量取决于最短的木板，这里容量取决于最矮的高度)，即min(height[i], height[j])，宽就是两个高度在横坐标上的坐标距离，即j - i。

暴力枚举

首先尝试了一下暴力枚举计算，时间复杂度O(n^2)。

pub fn max_area_bruces_force(height: Vec<i32>) -> i32 {
    let mut max = 0;
    let len = height.len();
    for (i, value) in height.iter().enumerate() {
        for j in 1..len {
            let curr = (*value).min(height[j]) * (j as i32 - i as i32);
            max = max.max(curr);
        }
    }
    max
}

上面这种，就是简单的两层循环遍历，枚举出所有的可能，并选出最大值。(必然，是过不了的，运行超时)。

双指针解法O(n)

上面O(n^2)的解法，其实是固定左边的柱子，从左向右移动右边的柱子。

假设当前两个指针在i和j(i≥0, j< len(height), i<j)，面积计算为s，面积的计算公式：

S = min(height[i], height[j]) * (j - i)

我们用(i,j)来表示这种情况。接下来考虑如何移动i和j。接下来继续移动i和j，i只能往右移，即 i+=1，j只能往左移，即j-=1。

情况1： height[i] < height[j]

如果移动j，移动后记作(i, j-1), 这种情况的面积： min(height[i], height[j-1]) * (j - 1- i)。首先，移动后的高，h = min(height[i], height[j-1]), 肯定是小于等于移动前的高度height[i], 而乘号右边的宽是小于(i,j)时的。所以这种移动情况可以排除。

如果移动i，移动后的面积 min(height[i+1], height[j]) * (j - 1- i)，和(i,j）相比，min(height[i+1],height[j]) 和 min(height[i], height[j])相比，当height[i+1] > height[i]时，可能得到更大面积的。

通过上面的简单推理，可以确定算法如下：

使用两个指针，分别从0 和 len(height)开始；
移动高度较矮的指针。

Rust版本代码：

pub fn max_area(height: Vec<i32>) -> i32 {
    let mut left = 0;
    let mut right = height.len() - 1;
    let mut max = 0;

    while left < right {
        let curr_area = height[left].min(height[right]) * (right - left) as i32;
        max = max.max(curr_area);
        if height[left] < height[right] {
            left+=1;
        } else {
            right-=1;
        }
    }

    max
}

Java版本代码:

public int maxArea(int[] height) {
    int max = 0, left = 0, right = height.length - 1;
    while (left < right) {
        max = Math.max(
						Math.min(height[left], height[right]) * (right - left), 
						max);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return max;
}

「真诚赞赏，手留余香」

Leetcode.11 Container With Most Water 盛最多水的容器