花花酱 LeetCode 42. Trapping Rain Water - 刷题找工作 EP300

[@haochenzhang4429]

花花我觉得stack的方法其实也最好说一下。虽说是dp演化过来但是算水体积的时候变成了横向计算，算法还是有点不同的

[@lyon7481]

感谢花花，把dp这个playlist都看了，题也都刷了一遍，现在遇到常见pattern的dp题目都差不多能做出了。等刷过700题就去试试外企。

[@yuxueyuan]

你好棒！向你学习～

[@luzengyuan5326]

great explanation. Thanks

[@lgodlike2324]

乾貨滿滿 謝謝您

[@qingdeng6391]

这期的代码字体大小太棒了！手机也能看清

[@jerryliu2087]

woc，确实只要从小的那一边记录水体积，因为不管后面高度怎么样，当前记录的这一个都是不受影响的

[@idiot7leon]

讲得很清楚 真过瘾 感谢

[@liangbinchen2519]

花花酱的解法比leetcode的答案好理解多了

[@zzx6341193]

能不能帮忙看下我这个two pointer approach 的python code错在哪里啊？是个无限循环loop,我不知道怎么修改。(我不是用的leetode上那个class solution) def calc_rain_water(h): if len(h) == 0: return 0 left = 0 right = len(h) - 1 max_l = h[left] max_r = h[right] ans = 0 while left < right: if max_l < max_r: ans += max_l - h[left] max_l = max(max_l, h[left]) left += 1 else: ans += max_r - h[right] max_r = max(max_r, h[right]) left -= 1 return ans

[@HuaHuaLeetCode]

left -= 1 => right -= 1

[@nicknie4104]

除了huahua 回复的之外，更重要的是要把, left+=1和right-=1分别都上移一行。 如果放在之后的话max_l - h[left] or max_r - h[right]可能会小于0， 就不对了

[@chang8106]

换了4k屏 可以看最高清画质了

[@yiouli5245]

这道题从暴力到动归的思路是用记忆避免重复运算，和典型的动归思路（递归求解子问题）不一样，不知道用记忆避免重复算不算动归？

[@LUN-bo2fb]

動態規劃本來就有重複使用子問題的答案的特性(記憶)

[@rollercoasterer]

讲讲这题升级版407？多谢

[@IcepointEvo]

怎么缺了一个单调栈了

[@XXX-nd2zz]

題外話 花花 你的聲音好像有點不太一樣😅