草庐IT

【leetcode刷题】--- 我遇到一道很坏很坏的题~

翼同学 2023-09-01 原文

🔥系列专栏：【Leetcode】刷题与总结

目录

前言

今天在Leetcode上刷题，看到一道题很有趣。我乍一看，没有思路，但是仔细想了想，还是没思路。。。。哈哈，开个玩笑。

当我写出后解法后，系统老是提醒超出时间限制，太难了，努力想了好久，优化解法后终于通过了！还挺有成就感。

后来在官方的解法中，我又学到了其他的解题方法，解题的思路非常棒，所以就有了这篇文章，想和大家分享一下。

题目

✨描述:

  • 给定一个数组height，数组里有 n个非负整数

  • 每个元素都表示一个宽度为 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 个单位的雨水（蓝色部分表示雨水）

普通解法

🌱思路一

  • 刚开始我的想法是，只要求出每一列上能存放的雨水量，再加起来就行
  • 需要注意的是，最两端的柱子是不用考虑的，因为也不可能有雨水
  • 下面举两个例子来解释一下我的思路

举例一：

由上图可知，若想求A列上的雨水，则可发现：

  • A两侧最高的列分别是B和C
  • 显然B比C矮
  • 那么A上接到的雨水量为B-A
  • 也就是说，A上的雨水量为2

举例二：

由上图可知，若想求A列上的雨水，则可发现：

  • A两侧最高的列分别是B和C
  • 显然B比C矮
  • 但是此时的B比A还要矮
  • 那么A上并不能接到雨水

总结：

  • 我们可以对每一列上的雨水量进行计算（最两端的柱子不考虑），最后相加即可。

  • 需要遍历数组，对每一列A的左右两侧B，C中，取出较矮的那一列，减去A列的高度就能求出A上接到的雨水量（如例子一）

  • 但是如果B,C较矮的那一列比A还要矮，那么A上就没有雨水。（如例子二）

🌳代码

这是刚开始我写的代码：

但是超出了时间限制：

虽然这个思路不错，但是太耗时间了，通过不了。

那怎样能减低时间复杂度？

当我们分析后发现，上述代码之所以时间复杂度高，是因为对于计算每一列上的雨水量，都必须向两边寻找最大值，这就很耗费时间。

但是，我们可以利用动态规划，先知道每个位置的两侧的最大值是多少，那么就能够更加快速的求出接到的雨水量。也就是说，提前储存每个位置上左边所有柱子中的最大值，以及右边所有柱子中的最大值。

这该如何实现呢？

思路如下：

  • 我们可以定义两个数组B和C
  • 当1 <= i <= n-1时，在B[i]表示下标i及其i左边的柱子中的最大值
  • 正向遍历数组height，得到B[]
  • 当0 <= j <= n-2时，在C[j]表示下标j及其j右边的柱子中的最大值
  • 反向遍历数组height，得到C[]
  • 最后遍历数组height，对于每个柱子，计算接到的雨水值，和之前那个超时的算法差不多。

很幸运！通过了。

那么问题来了，还能想到什么解法呢？

想了很久后，思路二出现了。

🌱思路二

看下图：

  • 我们先找出数组中柱子高度的最大值。
  • 然后乘以数组的大小，得到了一个长方形。
  • 求出这个长方形的面积后，减去白色部分和黑色部分的面积后，就可以得到雨水量！

所以整理一下思路

写出代码如下：

通过了！

其他解法

接下来，我们来欣赏一下其他超棒的解法！

🌱思路三

思路三是利用单调栈的思想。

下面是来自LeetCode官方题解：

代码实现如下：

🌱思路四

思路四是利用双指针的思想。

同样也是官方的解法。

具体如下：

写在最后

说实话，遇到这道很坏很坏的题，确实体会到很多，其中一点就是我好菜。。。

随着刷题次数增加后，当我回过头来看今天记录的这道难题，希望能够更加轻松，彻底的理解与掌握。

对于这道题，你有什么想法呢，欢迎到评论区一起讨论，分享你的解法吧！！！

leetcode很strongcodexff学习c++后端刷题

有关【leetcode刷题】--- 我遇到一道很坏很坏的题~的更多相关文章

  1. ruby - 通过 RVM (OSX Mountain Lion) 安装 Ruby 2.0.0-p247 时遇到问题 - 2

    我的最终目标是安装当前版本的RubyonRails。我在OSXMountainLion上运行。到目前为止，这是我的过程:已安装的RVM$\curl-Lhttps://get.rvm.io|bash-sstable检查已知(我假设已批准)安装$rvmlistknown我看到当前的稳定版本可用[ruby-]2.0.0[-p247]输入命令安装$rvminstall2.0.0-p247注意:我也试过这些安装命令$rvminstallruby-2.0.0-p247$rvminstallruby=2.0.0-p247我很快就无处可去了。结果:$rvminstall2.0.0-p247Search

  2. ruby - 安装 Ruby 时遇到问题(无法下载资源 "readline--patch") - 2

    当我尝试安装Ruby时遇到此错误。我试过查看this和this但无济于事➜~brewinstallrubyWarning:YouareusingOSX10.12.Wedonotprovidesupportforthispre-releaseversion.Youmayencounterbuildfailuresorotherbreakages.Pleasecreatepull-requestsinsteadoffilingissues.==>Installingdependenciesforruby:readline,libyaml,makedepend==>Installingrub

  3. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  4. ruby - Nokogiri:遇到 nil:NilClass 错误 "undefined method ‘text’” - 2

    我是程序员的新手，请原谅我的新手。所以我正在使用Nokogiri来抓取警方的犯罪记录。这是下面的代码:require'rubygems'require'nokogiri'require'open-uri'url="http://www.sfsu.edu/~upd/crimelog/index.html"doc=Nokogiri::HTML(open(url))putsdoc.at_css("title").textdoc.css(".brief").eachdo|brief|putsbrief.at_css("h3").textend我使用选择器小工具书签来查找日志(.brief)的C

  5. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  6. ruby - 在 ubuntu 中安装 rvm 时遇到问题 - 2

    我刚刚使用以下命令在我的机器上安装了rvmbash在我的终端里得到了这个InstallationofRVMto/home/rahul/.rvm/iscomplete.当我转到/home/rahul/.rvm/时，我能够看到所有必要的文件夹，但是当我在终端中输入rvm命令时，出现此错误rvm--versionNocommand'rvm'found,butthereare19similaronesrvm:commandnotfound我该如何解决？编辑我还在我的bashrc中添加了以下几行if[[-n"$PS1"]];thenif[[-s$HOME/.rvm/scripts/rvm]];t

  7. ruby - 在我的 Mac 上安装 ruby​​ gem json 时遇到问题 - 2

    我在尝试通过ruby​​gems安装json模块时收到此警告。有什么想法吗？Mac-Minipoulh$sudogeminstalljsonPassword:WARNING:File'/System/Library/Frameworks/Ruby.framework/Versions/1.8/usr/lib/ruby/gems/1.8/specifications/json-1.2.0.gemspec'doesnotevaluatetoagemspecificationBuildingnativeextensions.Thiscouldtakeawhile...ERROR:Errori

  8. L2TP连接尝试失败，因为安全层在初始化与远程计算机的协商时遇到了一个处理错误 - 2

    废话不多先看bug解决方案在下面！！！！启动服务查看服务是否开启首先我的电脑-右键-管理-服务和应用程序-服务-找到IPsecPolicyAgent-右键属性-启动方式改为自动，并重启服务，如下图打开设置-更改适配器选项如下图点击连接失败的连接-右键-属性-安全-允许使用这些协议编辑注册表按Ctrl+R打开命令行窗口输入regedit打开注册表输入下面命令进入以下页面HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\RasMan\Parameters如下图在右侧编辑菜单上，鼠标右键新建，然后单击DWORD(32)位值。键入Prohibit

  9. Java调用ffmpeg处理视频，并记录下遇到的坑 - 2

    目录需求基于JavaCV跨平台执行ffmpeg命令[^1]坑一内存不足坑二多个ffmpeg进程并行导致IO负载大，进而导致ioerror?坑三使用Java操作ffmpeg时，有时会卡死坑四Process的waitFor死锁问题及解决办法需求给透明背景的视频自动叠加一张背景图片基于JavaCV跨平台执行ffmpeg命令1我测试发现的本需求的最小依赖：dependency>groupId>org.bytedecogroupId>artifactId>ffmpeg-platform-gplartifactId>version>5.0-1.5.7version>dependency>核心代码：Stri

  10. ruby - 在 OS X Mavericks 上降级 Ruby 时遇到问题 - 2

    OSX10.9附带ruby​​2.0.0p195，但我需要安装Ruby1.8.7。我一直遇到错误。我安装了Xcode5-DP，我相信也安装了命令行工具。在终端中:sudorvminstall1.8.7Searchingforbinaryrubies,thismighttakesometime.Nobinaryrubiesavailablefor:osx/10/x86_64/ruby-1.8.7-p371.Continuingwithcompilation.Pleaseread'rvmmount'togetmoreinformationonbinaryrubies.Installingr

随机推荐