LeetCode_11_ContainerWithMostWater

2019 年 04 月 05 日

832 次浏览

4059字数

1. 题目描述

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 and n is at least 2.

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.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

2. 解题

刚开始拿到这道题还是有点懵的，毕竟没做过多少这种把算法和实物结合起来的题，一时间脑子转不过弯来，不过冷静下来稍微看看，还是很容易看出一个暴力解法的，就是两层循环遍历每一个元素，遍历一遍所有可能的组合然后找出最大面积就行了。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))

// 两层循环
int maxArea(int* height, int heightSize) {
    int maxArea = 0;
    int newArea = 0;
    int i, j;

    for (i = 0; i < heightSize; i++) {
        for (j = i + 1; j < heightSize; j++) {
            newArea = (j - i) * MIN(height[i], height[j]);
            maxArea = MAX(newArea, maxArea);
        }
    }

    return maxArea;
}

int main() {
    int arr[] = { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
    printf("%d\n", maxArea(arr, 9));

    system("pause");
    return 0;
}

3. 进阶

这道题其实还是很有意思的，当然不是说我上面那个O(N^2)的解法有意思，有意思的是这题居然还有一个O(N)的解法，真是惊为天人，下面先介绍一下这个解法的过程。

首先来两个指针left和right，left指向数组首元素，right指向数组尾元素

记录一下此时的left和right两根棍所组成的矩形的面积。

然后left和right都是向中间移动，具体的移动规则是：比较left和right所表示的棍的长度，如果left棍比right棍短，则left向右移动一步，否则right向左移动一步，每移动一次再计算一下此时矩形的面积，然后重复上述步骤，直到两个指针相遇。

下面用图来描述一下这个过程。

下一步两个指针相遇，循环结束。先说下结论：用这样的方式移动指针，一定可以在两个指针相遇之前找到题目中需要的最大面积。也就是上面移动过程中的某一步，left和right所组成的棍一定是所求的最大面积。

然后自然就是why了，为什么用这种方法一定可以找到最大面积？我们用神奇的反证法证明这个问题。

首先画一个简图，假设图里两根红线就表示的是最大面积所对应的那两条边，然后我们开始遍历，还是先来left指针和right指针。

根据我们上面所说的指针移动的法则，我们可以想到left和right指针中一定有一个指针先接触到两根红线中的一个，而另一个指针还没接触到任何一根红线，在我们这个例子中就是left指针先接触到左边的红线，而right指针还没动过。

对于现在的情况，我们知道此时必须right指针一直往左走走到右边的红线上，而left指针在这个过程中没有动，才能让两个指针同时指向两根红线，也就是找到最大面积。如果left指针在right指针移动到右红线之前就又往右移动了，那么就决不可能找到最大面积。

那么现在分析，什么情况下left会向右移动呢，根据我们的移动规则，就是right指向的棍比left指向的棍更长，left就会向右移动，也就是说，right在移动到右红线之前，找到了一根比左红线还长的棍，导致了left右移从而永远也找不到最大面积。但是，用反证法，如果右红线右边有比左红线还长的棍，那么最大面积就不是两个红线所表示的矩形了，而应该是左红线与那条更长的线所表示的矩形！（请自行证明）这就与之前的假设相违背了，也就不可能发生。换句话说，right在向左移动的时候，一定不可能遇到一根比左红线还长的线，直到right指向右红线，此时两个指针指向两条红线，我们就得到了最大面积！

代码：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))

int maxArea_ON(int* height, int heightSize) {
    int left = 0, right = heightSize - 1;
    int maxArea = 0, newArea = 0;

    while (left != right) {
        newArea = (right - left) * MIN(height[left], height[right]);
        maxArea = MAX(newArea, maxArea);
        (height[left] < height[right]) ? ++left : --right;
    }

    return maxArea;
}

int main() {
    int arr[] = { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
    printf("%d\n", maxArea_ON(arr, 9));

    system("pause");
    return 0;
}

当然这个神奇的反证法不是我这个数学渣能想出来的，在这里写反证法也只是因为反证法简单，评论区还有大神正着证明或者用图表证明的，那些方法我甚至连他们说的英语都看不懂。。。

下面贴上写这个反证法的大佬的原文

LeetCode_11_ContainerWithMostWater