让我们一起啃算法----盛最多水的容器

盛最多水的容器(Container-With-Most-Water)

题干如下:

给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明:你不能倾斜容器,且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例:
  输入:[1,8,6,2,5,4,8,3,7]
  输出:49
来源:力扣

根据题意,将题目抽象为数学模型:给定一个 数组array两个索引X、Y,在随意移动 X、Y 的过程中,求 S = |Y-X| * Min( array[X], array[Y] ) 的最大值,其中 Min( array[X], array[Y] ) 记为 H

  1. |Y-X| 表示索引差值的绝对值
  2. Min( array[X], array[Y] ) ,是因为在 |Y-X |固定的前提下,容器的纳水量完全取决于较小的高度,所以这边取 Min。

解题思路

我们将 X 指向数组的第一个位置Y 指向数组的最后一个位置。按照上面的公式求出 S 的值并记录。判断 array[X] 和 array[Y] 的值,如果 array[X] > array[Y] 则 Y 向左移动,如果 array[X] < array[Y] 则 X 向右移动,如果 array[X] = array[Y] 则 X 向右移动,Y 向左移动。总之,索引指向的元素值较小的移动,如果相等则一起移动。解释如下:

假设 X 指向的元素为 2,Y 指向的元素为 7。由于 2 比 7 小,所以 X 向右移。至于为什么不是 Y 向左移动是因为 H的值 是 array[X] 和 array[Y] 中较小的值,如果将 Y 向左移动,假设 array[Y-1] 比 array[X] 大,这时 H的值 仍为 array[X],而(Y - X)的值却变小了,因此 S 也变小了。假设 array[Y-1] 比 array[X] 小,这时 H的值 为 array[Y-1] ,较之前变小了,并且 (Y - X)的值也变小了,因此 S 也变小了。所以要移动元素值较小的索引。如果 array[X] 和 array[Y] 相等,则 X 和 Y 一起移动,分析过程与不相等一致。

流程图分析如下:

代码实现

GO语言实现

func maxArea(height []int) int {
    var (
        i         = 0
        j         = len(height) - 1
        max       = 0
        minHeight = 0
    )

    for i < j {
        // H 的 计算
        if height[j] > height[i] {
            minHeight = height[i]
        } else {
            minHeight = height[j]
        }

        // 记录面积,也就是纳水量
        newMax := (j - i) * minHeight
        if newMax > max {
            max = newMax
        }

        // 移动高度小的指针,如果相等则一起移动
        if height[j] > height[i] {
            i++
        } else if height[j] < height[i] {
            j--
        } else {
            j--
            i++
        }
    }
    return max
}

思考

这题是我个人比较喜欢的,解题的过程很像自己在做职业规划时权衡利弊的模样。 H的值 好比职业技能的深度,|Y-X|的值 好比职业技能的广度,S的值 好比职场的价值,价值是由广度和深度一起决定的。有时候如果无法在深度上有提升,不必死磕,试试扩展一下广度。

总结

每天进步一点点,加油!
算法教程项目,每天更新一题,点个 star 支持一下呀
https://github.com/wx-satellite/learning-a...

本作品采用《CC 协议》,转载必须注明作者和本文链接
三斤
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 2

厉害

4年前 评论
三斤和他的喵 (楼主) 4年前
huxiaochu 4年前
captain2021 (作者) 4年前
function maxArea($nums) {
    $i= 0;
    $j = count($nums) - 1;
    $max = 0;
    while ($i < $j) {
        if ($nums[$j] > $nums[$i]) {
            $minHeight = $nums[$i];
        } else {
            $minHeight = $nums[$j];
        }

        // 记录面积
        $newMax = ($j - $i) * $minHeight;
        if ($newMax > $max) {
            $max = $newMax;
        }

        // 移动高度小的指针,如果相等则一起移动
        if ($nums[$j] > $nums[$i]) {
            $i++;
        } elseif ($nums[$j] < $nums[$i]) {
            $j--;
        } else {
            $j--;
            $i++;
        }
    }

   return $max;
}

echo maxArea([1,8,6,2,5,4,8,3,7]); // output: 49

用 php 实现了一下 @huxiaochu 主要是两个指针,分别从头和尾开始移动,然后面积是两者直接的间距 * 较小的那个数字,加一层判断,如果从前面开始移动的大于从后面开始移动的,就继续移动后面的那个,相反同理,如果两个相等,就一起移动,每次计算面积,本次大于上次,就将暂存的最大面积值替换掉

4年前 评论
Littlesqx 4年前
三斤和他的喵 (楼主) 4年前
huxiaochu 4年前
captain2021 (作者) 4年前
Littlesqx 4年前
captain2021 (作者) 4年前

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!