【LeetCode】42.接雨水

news/2024/11/14 22:02:21/

接雨水

题目描述:

        给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

示例 1:

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 

示例 2:

输入:height = [4,2,0,3,2,5]
输出:9

提示:

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

思路分析:

作为力扣的经典hard题和面经的常考题,本题的的解法也是非常多样。下面列举几种常见解法:

解法一:按行求

        整个思路就是,求第 i 层的水,遍历每个位置,如果当前的高度小于 i,并且两边有高度大于等于 i 的,说明这个地方一定有水,水就可以加 111。

        如果求高度为 i 的水,首先用一个变量 temp 保存当前累积的水,初始化为 000。从左到右遍历墙的高度,遇到高度大于等于 i 的时候,开始更新 temp。更新原则是遇到高度小于 i 的就把 temp 加 111,遇到高度大于等于 i 的,就把 temp 加到最终的答案 ans 里,并且 temp 置零,然后继续循环。

image.png

        但这个解法现在 AC 不了了,会报超时,也就不展示代码了

解法二:按列求

        求每一列的水,我们只需要关注当前列,以及左边最高的墙,右边最高的墙就够了。至于装水的多少,当然根据木桶效应,我们只需要看左边最高的墙和右边最高的墙中较矮的一个就够了。

所以,根据较矮的那个墙和当前列的墙的高度可以分为两种情况。

  • 较矮的墙的高度大于当前列的墙的高度
  • 较矮的墙的高度小于等于当前列的墙的高度

只有当较矮的墙的高度大于当前列的墙的高度时才能存水,存水量为矮的墙的高度减去当前列的墙的高度。

image.png

代码展示:
class Solution {
public int trap(int[] height) {int sum = 0;//最两端的列不用考虑,因为一定不会有水。所以下标从 1 到 length - 2for (int i = 1; i < height.length - 1; i++) {int max_left = 0;//找出左边最高for (int j = i - 1; j >= 0; j--) {if (height[j] > max_left) {max_left = height[j];}}int max_right = 0;//找出右边最高for (int j = i + 1; j < height.length; j++) {if (height[j] > max_right) {max_right = height[j];}}//找出两端较小的int min = Math.min(max_left, max_right);//只有较小的一段大于当前列的高度才会有水,其他情况不会有水if (min > height[i]) {sum = sum + (min - height[i]);}}return sum;
}
}

解法三: 动态规划

        在解法二中,对于每一列,我们求它左边最高的墙和右边最高的墙,都是重新遍历一遍所有高度,这里我们可以优化一下。用两个数组记录当前每个列的左右最大值,避免重复遍历。

class Solution {public int trap(int[] height) {int sum = 0;//用来存放当前的左端最大值int[] max_left = new int[height.length];//用来存放当前的右端最大值int[] max_right = new int[height.length];//如果即将存入的的高度大于当前左端最大值,则替换最大值for (int i = 1; i < height.length - 1; i++) {max_left[i] = Math.max(max_left[i - 1], height[i - 1]);}//如果即将存入的的高度大于当前右端最大值,则替换最大值for (int i = height.length - 2; i >= 0; i--) {max_right[i] = Math.max(max_right[i + 1], height[i + 1]);}//找出两端较小的,只有较小的一段大于当前列的高度才会有水,其他情况不会有水for (int i = 1; i < height.length - 1; i++) {int min = Math.min(max_left[i], max_right[i]);if (min > height[i]) {sum = sum + (min - height[i]);}}return sum;}
}

解法四:双指针

        动态规划中,我们常常可以对空间复杂度进行进一步的优化。例如这道题中,可以看到,max_left [ i ] 和 max_right [ i ] 数组中的元素我们其实只用一次,然后就再也不会用到了。所以我们可以不用数组,只用两个指针就行了。

首先比较当前列左右两墙的高度大小,将那个较小的与当前列进行比较

class Solution {public int trap(int[] height) {int sum = 0,maxleft = 0,maxright = 0;//左指针加进去int left = 1;// 加右指针进去int right = height.length - 2; for (int i = 1; i < height.length - 1; i++) {//如果左指针的前一个值小于右指针的后一个值if (height[left - 1] < height[right + 1]) {//那么从左到右更,记录当前左端最大值maxleft = Math.max(maxleft, height[left - 1]);//如果当前左指针指向的高度小于左墙,则两者的高度差即为存水量if (maxleft > height[left]) {sum = sum + (maxleft - height[left]);}left++;} //否则从右到左更,记录当前右端最大值else {maxright = Math.max(maxright, height[right + 1]);//如果当前右指针指向的高度小于右墙,则两者的高度差即为存水量if (maxright  > height[right]) {sum = sum + (maxright  - height[right]);}right--;}}return sum;}
}

http://www.ppmy.cn/news/1468688.html

相关文章

PostgreSQL中有没有类似Oracle的dba_objects系统视图

PostgreSQL中有没有类似Oracle的dba_objects系统视图 在PostgreSQL中&#xff0c;没有一个完全集成了所有对象信息的视图&#xff08;类似于Oracle中的DBA_OBJECTS&#xff09;。但是&#xff0c;PostgreSQL提供了一些系统目录表和视图&#xff0c;可以用来获取数据库对象的信…

机器学习笔记 - stable diffusion web-ui安装教程

一、Stable Diffusion WEB UI 屌丝劲发作了,所以本地调试了Stable Diffusion之后,就去看了一下Stable Diffusion WEB UI,网络上各种打包套件什么的好像很火。国内的也就这个层次了,老外搞创新,国内跟着屁股后面搞搞应用层,就叫大神了。 不扯闲篇了,我们这里从git源码直接…

mac配置Personal Access Tokens

背景 在macbook环境中&#xff0c;使用idea、android studio、xcode时&#xff0c;使用gitlab需要登录&#xff0c;而直接使用文明密码是不允许登录的&#xff0c;这时就需要换种方式&#xff0c;这里有两种&#xff1a;ssh、Access Tokens&#xff0c;在公用电脑上推荐使用Ac…

[译文] LLM安全:3.网络LLM攻击及提示注入知识普及(PortSwigger)

这是作者新开的一个专栏&#xff0c;主要翻译国外知名安全厂商的技术报告和安全技术&#xff0c;了解它们的前沿技术&#xff0c;学习它们威胁溯源和恶意代码分析的方法&#xff0c;希望对您有所帮助。当然&#xff0c;由于作者英语有限&#xff0c;会借助LLM进行校验和润色&am…

【简单探索微软Edge】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

Go语言中,公司gitlab私有仓库依赖拉取配置

为什么要考虑私有仓库 Go语言目前都已经采用了官方统一的 go modules 来管理依赖&#xff0c;后续也不太可能出现比较乱的生态&#xff0c; 因此了解下如何让这个依赖管理正常工作是非常必要的。 对于Github或者其他公有仓库&#xff0c;依赖管理是非常直接和方便的,设置好GO…

LeetCode | 1470.重新排列数组

class Solution(object):def shuffle(self, nums, n):""":type nums: List[int]:type n: int:rtype: List[int]"""result []for i in range(n):result.append(nums[i])result.append(nums[i n])return result这题很容易想到的就是遍历整个数组…

手撕设计模式——克隆对象之原型模式

1.业务需求 ​ 大家好&#xff0c;我是菠菜啊&#xff0c;前俩天有点忙&#xff0c;今天继续更新了。今天给大家介绍克隆对象——原型模式。老规矩&#xff0c;在介绍这期之前&#xff0c;我们先来看看这样的需求&#xff1a;《西游记》中每次孙悟空拔出一撮猴毛吹一下&#x…