介绍

总而言之是时候利用暑假锻炼一下算法技术，一提算法面试就面露难色的情形总不能一直持续下去。本栏目面向有一定基础的编程爱好者，每天（如果up不鸽）分享并解析一道LeetCode中高难度题目（通常是hard）。有兴趣的小伙伴可以一起跟着做并且讨论解法。目前的教材是花花酱的Leetcode Problem List【1】.

适合人群：

有一定算法基础，但是还未能顺利通过笔试/面试，总觉得算法题目想不明白的你。

不适合人群：

算法入门级选手（一上来就做难题可能并不合适，建议首先专注简单/中等题目）

非常不适合人群：

算法竞赛选手（这种小儿科的问题完全是在浪费您的时间）

过往题目在这里！

接雨水

题目看这里，leetcode第四十二题，hard难度：
https://leetcode.com/problems/trapping-rain-water/

强烈建议读者自己先做（不过真的会有读者吗，笑），有任何问题欢迎在评论区讨论，up看到了会及时回复。做完了欢迎在评论区打卡～

解析

这道题目作为一道经典的难度题目，十分值得深入研究。其中的单调栈虽然一开始可能让人感到陌生，但只要熟悉了这个概念，其实并不复杂。题目的难点主要有两个方面。

首先，我们在栈中存储的是数组元素的索引，而非其实际的高度。这样做的原因在于，我们需要用这些索引来计算可以储存雨水的区域的宽度。

其次，理解从栈中取出元素来获取左边界的逻辑是一大难点。如果我们只关注当前栈顶元素的高度，可能会陷入死胡同。举例来说，如果当前栈顶的高度是3，新的高度是5，两者的索引差为4。如果我们只是简单地计算（5-3）*4，这将导致问题——我们如何能确定在3和5之间的最小高度始终为0呢？因此，我们需要将注意力转向当前的高度，并从栈顶向左寻找合适的边界。这就是这道题目真正困难之处所在。

当然了，现代面试应该没人考这道题目，面试官应该默认你都背下来了。不过还是值得一做。

思考乐园

如果在获得储水池底部之后发现栈是空的，这代表什么？是否依然应该计算储水区域的体积？欢迎把答案写在评论区。

音乐推荐

今天又是躺平的一天......接下来说不定要多在家里远程干活，每天花四个小时在通勤上再怎么说也太让人疲惫了。这首来自安婧_Tiffany的阿拉斯加海湾送给因为每周二十个小时的通勤而疲惫不堪的你，希望你的心灵得到抚慰。

教材链接

【1】https://zxi.mytechroad.com/blog/leetcode-problem-categories/