1. 题目描述

problem link

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;
}

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

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

Last modification:September 8th, 2019 at 08:25 pm