Container With Most Water（最大水容器）

翻譯

給定 n 個(gè)非負(fù)整數(shù) a1,a2,...,an，其中每個(gè)代表一個(gè)點(diǎn)坐標(biāo)（i,ai）。

n 個(gè)垂直線段例如線段的兩個(gè)端點(diǎn)在（i,ai）和（i,0）。

找到兩個(gè)線段，與 x 軸形成一個(gè)容器，使其包含最多的水。

備注：你不必傾倒容器。

原文

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.

Note: You may not slant the container.

題目的意思是，數(shù)組中的每個(gè)數(shù)對(duì)應(yīng)一條線段的長(zhǎng)度，索引對(duì)應(yīng) x 坐標(biāo)，兩個(gè)索引可以組成一個(gè)底部的寬，高度就是前面所說(shuō)的線段的長(zhǎng)度，而既然是要盛水，高度就是兩個(gè)線段中較短的一個(gè)。

那么該怎么去解題呢？

我水平不行，英文也不行，所以每次一開(kāi)始都是用最簡(jiǎn)單的方法，旨在試試有沒(méi)有理解題目的意思，即便超出時(shí)間 / 空間限制也沒(méi)事。

public int MaxAera(int[] height)
{
    int area = 0;
    for (int i = 0; i < height.Length; i++)
    {
        for (int j = i + 1; j < height.Length; j++)
        {
            if (height[i] < height[j])
                area = Math.Max(area, countArea(height, i, j));
        }
    }
    return area;
}

public int countArea(int[] height, int x, int y)
{
    int h = height[x] > height[y] ? height[x] : height[y];
    int info = h * (y - x);
    return info;
}

很明顯這樣是不行的……

那有那些部分可以簡(jiǎn)化呢？

前面的方法是從數(shù)組左側(cè)開(kāi)始逐個(gè)向右遍歷所有情況，但明顯可以從兩側(cè)向中間進(jìn)發(fā)，通過(guò)對(duì)應(yīng)的 max 函數(shù)來(lái)保留最大的面積。

當(dāng)從左邊進(jìn)入到圖中線段 1 位置，右邊進(jìn)入到線段 5 的時(shí)候。你不會(huì)想著右邊繼續(xù)進(jìn)入線段 6 和 7，因?yàn)槟憔褪菑哪沁呥^(guò)來(lái)的。

那么是該左邊的往右走，還是右邊的往左走呢？

如果是右邊的往左走，雖然線段 1 變成了線段 2，但是線段1到線段5的距離比線段 2 大，因此面積也大。所以走了之后面積反而小了。

如果是右邊的往左走，親自行腦補(bǔ)：線段 3 和線段 4 是在同一位置，如果是到了線段 4，那么容器的高度將從原本的線段 5 的長(zhǎng)度變成線段 1 的長(zhǎng)度，（雖然由于距離的變小，總面積仍可能變小，但請(qǐng)繼續(xù)往下看），而如果到了線段 3，雖然高度變小了，寬度變小了，但，那又何妨呢？因?yàn)槟愕?maxArea 還是在那里的，每次的計(jì)算后，當(dāng)且僅當(dāng)高度超過(guò)原本的高度之后才會(huì)覆蓋原來(lái)的值。

maxArea = Max(maxArea,newArea);

也就是說(shuō)，高度如果沒(méi)有超過(guò)，就沒(méi)有什么影響。

http://wiki.jikexueyuan.com/project/leetcode-book/images/2.png" alt="" />

至于你說(shuō)它會(huì)不會(huì)因?yàn)樽栽龊妥詼p而發(fā)生越界，如果

int[] height = {10, 1, 2, 3, 4, 5, 6, 7, 11};

假設(shè)這里的 10 和 11 對(duì)應(yīng)線段 1 和線段 6，請(qǐng)自行腦補(bǔ)：去掉線段 7，既然線段 1 短于線段 6，那么發(fā)生的是 left++，而不是 left–。所以，并不會(huì)越界的。反之，亦然。

public class Solution
{
    public int MaxArea(int[] height)
    {
        int left = 0, right = height.Length - 1;
        int maxArea = 0;
        while (left < right && left >= 0 && right <= height.Length - 1)
        {
            maxArea = Math.Max(maxArea, Math.Min(height[left], height[right]) * (right - left));
            if (height[left] > height[right])
            {
                right--;
            }
            else
            {
                left++;
            }
        }
        return maxArea;
    }
}

明天繼續(xù)，加油！