[Leetcode 之 PHP 解析 (42. Trapping Rain Water)

简介: [Leetcode 之 PHP 解析 (42. Trapping Rain Water)

1668569051540.jpg

题目介绍


这道题挺有意思的,给定一个非负数的每个宽度为 1 的柱形图,问你下雨天能接多少雨水。例题中给定的数组能接的总数为 6,即图中蓝色部分。


题目分析


我们先来随便举个例子吧。例如示例中给出的数组第 6 位(也就是索引位置 5)高度为 0,此时这个位置能盛的水是 2。这个 2 是咋么算出来的呢。从当前位置往它的左边查找,查出最高的水位,即索引 3 (值为 2)。从当前位置往右边找出它的最高位,即索引位置 7 (值为 3),然后取他们中的最小值高度 min (2,3) 减去当前位置的高度 (0)=2。为什么取的是两者的最小值呢。很简单的道理,两边之间能盛的水的高度必然会和其中一边高度持平的,再高就溢出了。


代码实现


/**
 * @param Integer[] $height
 * @return Integer
 */
function trap($height)
{
    $res = 0;
    $size = count($height);
    for ($i = 1; $i < $size - 1; $i++) {
        $left = 0;
        $right = 0;
        for ($j = $i; $j >= 0; $j--) {
            $left = max($left, $height[$j]);
        }
        for ($j = $i; $j < $size; $j++) {
            $right = max($right, $height[$j]);
        }
        $res += min($left, $right) - $height[$i];
    }
    return $res;
}

你应该已经发现了,上面的执行时间是 O (n*n)。每一个位置我们都遍历查找了左右两边,仅仅是为了找最大值,我们为什么不把每个位置左右两边最大值一次存起来?


/**
 * @param Integer[] $height
 * @return Integer
 */
function trap($height)
{
    $res = 0;
    $size = count($height);
    $left[0] = $height[0];
    for ($i = 1; $i < $size; $i++) {
        $left[$i] = max($left[$i - 1], $height[$i]);
    }
    $right[$size - 1] = $height[$size - 1];
    for ($i = $size - 2; $i >= 0; $i--) {
        $right[$i] = max($right[$i + 1], $height[$i]);
    }
    for ($i = 1; $i < $size - 1; $i++) {
        $res += min($left[$i], $right[$i]) - $height[$i];
    }
    return $res;
}

其实上面的解题思路就是一个动态规划的过程。动态规划最重要的两步:1 是状态的定义,即上面的这两个定义:

$left[0] = $height[0];
$right[$size - 1] = $height[$size - 1];

第二步就是状态转移方程,即上面的

$left[$i] = max($left[$i - 1], $height[$i]);
 $right[$i] = max($right[$i + 1], $height[$i]);

其实动态规划就像是开启了上帝的视角,每次都能获取到全局的情况。经常用来解最优,最近,最少这类题目。你再进一步分析,好像动态规划的思想就是一个空间换时间的方案。第一个解的时间是 O (n 的平方),空间就一个变量 O (1)。再来看第二道解,时间是 O (n),空间是 O (n)。本质上来说就是空间换时间的方案。最后其实这道题还有其他能解的方案。。。。刷着刷着,乐趣就上来了。

目录
打赏
0
0
0
0
2
分享
相关文章
PHP技巧:解析JSON及提取数据
这就是在PHP世界里探索JSON数据的艺术。这场狩猎不仅仅是为了获得数据,而是一种透彻理解数据结构的行动,让数据在你的编码海洋中畅游。通过这次冒险,你已经掌握了打开数据宝箱的钥匙。紧握它,让你在编程世界中随心所欲地航行。
124 67
局域网屏幕监控软件 PHP 图像块增量传输算法解析
本文探讨了一种基于PHP语言开发的图像块增量传输算法,适用于局域网屏幕监控场景。通过将屏幕图像分块处理、计算哈希值并对比变化区域,该算法显著降低了网络带宽占用,提升了监控效率。在企业管理和远程教育中,该技术可实现终端设备的实时监控与远程管控,同时支持与生物识别等技术融合,拓展应用范围。实验表明,该算法在常规办公场景下可减少90%以上的数据传输量,展现了良好的实时性和优化效果。
33 3
|
2月前
|
Go
【LeetCode 热题100】155:最小栈(详细解析)(Go语言版)
本文详细解析了力扣热题155:最小栈的解题思路与实现方法。题目要求设计一个支持 push、核心思路是使用辅助栈法,通过两个栈(主栈和辅助栈)来维护当前栈中的最小值。具体操作包括:push 时同步更新辅助栈,pop 时检查是否需要弹出辅助栈的栈顶,getMin 时直接返回辅助栈的栈顶。文章还提供了 Go 语言的实现代码,并对复杂度进行了分析。此外,还介绍了单栈 + 差值记录法的进阶思路,并总结了常见易错点,如 pop 操作时忘记同步弹出辅助栈等。
85 6
内网监控桌面与 PHP 哈希算法:从数据追踪到行为审计的技术解析
本文探讨了内网监控桌面系统的技术需求与数据结构选型,重点分析了哈希算法在企业内网安全管理中的应用。通过PHP语言实现的SHA-256算法,可有效支持软件准入控制、数据传输审计及操作日志存证等功能。文章还介绍了性能优化策略(如分块哈希计算和并行处理)与安全增强措施(如盐值强化和动态更新),并展望了哈希算法在图像处理、网络流量分析等领域的扩展应用。最终强调了构建完整内网安全闭环的重要性,为企业数字资产保护提供技术支撑。
85 2
|
2月前
|
【LeetCode 热题100】17:电话号码的字母组合(详细解析)(Go语言版)
LeetCode 17题解题思路采用回溯算法,通过递归构建所有可能的组合。关键点包括:每位数字对应多个字母,依次尝试;递归构建下一个字符;递归出口为组合长度等于输入数字长度。Go语言实现中,使用map存储数字到字母的映射,通过回溯函数递归生成组合。时间复杂度为O(3^n * 4^m),空间复杂度为O(n)。类似题目包括括号生成、组合、全排列等。掌握回溯法的核心思想,能够解决多种排列组合问题。
65 11
|
2月前
|
【LeetCode 热题100】739:每日温度(详细解析)(Go语言版)
这篇文章详细解析了 LeetCode 第 739 题“每日温度”,探讨了如何通过单调栈高效解决问题。题目要求根据每日温度数组,计算出等待更高温度的天数。文中推荐使用单调递减栈,时间复杂度为 O(n),优于暴力解法的 O(n²)。通过实例模拟和代码实现(如 Go 语言版本),清晰展示了栈的操作逻辑。此外,还提供了思维拓展及相关题目推荐,帮助深入理解单调栈的应用场景。
94 6
|
3月前
|
【LeetCode 热题100】【二叉树构造题精讲:前序 + 中序建树 & 有序数组构造 BST】(详细解析)(Go语言版)
本文详细解析了二叉树构造的两类经典问题:通过前序与中序遍历重建二叉树(LeetCode 105),以及将有序数组转化为平衡二叉搜索树(BST,LeetCode 108)。文章从核心思路、递归解法到实现细节逐一拆解,强调通过索引控制子树范围以优化性能,并对比两题的不同构造逻辑。最后总结通用构造套路,提供进阶思考方向,帮助彻底掌握二叉树构造类题目。
188 9
【二叉树遍历入门:从中序遍历到层序与右视图】【LeetCode 热题100】94:二叉树的中序遍历、102:二叉树的层序遍历、199:二叉树的右视图(详细解析)(Go语言版)
本文详细解析了二叉树的三种经典遍历方式:中序遍历(94题)、层序遍历(102题)和右视图(199题)。通过递归与迭代实现中序遍历,深入理解深度优先搜索(DFS);借助队列完成层序遍历和右视图,掌握广度优先搜索(BFS)。文章对比DFS与BFS的思维方式,总结不同遍历的应用场景,为后续构造树结构奠定基础。
186 10
|
3月前
|
【LeetCode 热题100】73:矩阵置零(详细解析)(Go语言版)
这篇文章详细解析了力扣热题 73——矩阵置零问题,提供两种解法:一是使用额外标记数组,时间复杂度为 O(m * n),空间复杂度为 O(m + n);二是优化后的原地标记方法,利用矩阵的第一行和第一列记录需要置零的信息,将空间复杂度降低到 O(1)。文章通过清晰的代码示例与复杂度分析,帮助理解“原地操作”及空间优化技巧,并推荐相关练习题以巩固矩阵操作能力。适合刷题提升算法思维!
100 9
|
3月前
|
【LeetCode 热题100】394:字符串解码(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 394:字符串解码。题目要求对编码字符串如 `k[encoded_string]` 进行解码,其中 `encoded_string` 需重复 `k` 次。文章提供了两种解法:使用栈模拟和递归 DFS,并附有 Go 语言实现代码。栈解法通过数字栈与字符串栈记录状态,适合迭代;递归解法则利用函数调用处理嵌套结构,代码更简洁。两者时间复杂度均为 O(n),但递归需注意栈深度问题。文章还总结了解题注意事项及适用场景,帮助读者更好地掌握字符串嵌套解析技巧。
87 6

推荐镜像

更多
AI助理
登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问

你好,我是AI助理

可以解答问题、推荐解决方案等