leetcode11：盛最多水的容器（container-with-most-water）

carloscn commented 1 year ago

问题描述：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

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

示例 2：输入：height = [1,1] 输出：1 提示： n == height.length 2 <= n <= 105 0 <= height[i] <= 104

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/container-with-most-water

carloscn commented 1 year ago

解题思路：

对O(n)的算法，一开始两个指针一个指向开头一个指向结尾，此时容器的底是最大的，接下来随着指针向内移动，会造成容器的底变小，在这种情况下想要让容器盛水变多，就只有在容器的高上下功夫。那我们该如何决策哪个指针移动呢？我们能够发现不管是左指针向右移动一位，还是右指针向左移动一位，容器的底都是一样的，都比原来减少了 1。这种情况下我们想要让指针移动后的容器面积增大，就要使移动后的容器的高尽量大，所以我们选择指针所指的高较小的那个指针进行移动，这样我们就保留了容器较高的那条边，放弃了较小的那条边，以获得有更高的边的机会。

上述算法会不会错过最优解？上面描述里，我们每次只移动一步，去掉的各种都是比当前面积更小的，在这种情况下，我们把整个数组处理完，肯定是可以找到最优解的

当height(start) == height(end)的时候，该怎么做？当遇到height(start) == height(end)的时候，alba的做法是start++，其实我个人感觉可以start++和end--一起做了，还是上面的逻辑，我们start++后，由于end没有--，不会有机会得到更大的盛水量，只有start++和end--一起做了，才会有这个机会。

static int32_t max_area(int64_t *array, size_t sz, int64_t *out)
{
    int32_t ret = 0;
    int64_t mx_area = 0, area = 0;
    size_t x = 0, y = sz - 1;

    UTILS_CHECK_LEN(sz);
    UTILS_CHECK_PTR(array);

    if (2 >= sz) {
        *out = utils_int64_abs(array[x] - array[y]);
        goto finish;
    }

    while (x != y) {
        area = (y - x) * MIN(array[x], array[y]);
        mx_area = MAX(area, mx_area);
        if (array[x] > array[y]) {
            y --;
        } else if (array[x] < array[y]){
            x ++;
        } else {
            y --;
            x ++;
        }
    }

    *out = mx_area;

finish:
    return ret;
}

carloscn commented 1 year ago

code:

https://github.com/carloscn/structstudy/blob/master/c_programming/array/21_container-with-most-water_11.c

carloscn / structstudy