树作为重要的数据结构,在很多领域有着重要的用途。在LeetCode中对数的考察主要分为三个方面,一是树的遍历,二是BST(二叉搜索树),三是和树相关的算法。有时,树也常常被看做一个图,做BFS和DFS,树的考察是相当灵活的。这篇博客就这些问题做部分小结。…

        一种结合链表和优先队列的优雅解法,巧妙之处在于使用优先队列出队元素,可以直接得到下一个入队元素,算法复杂度是O(nlgn)。联想到如果不是优先队列结构,那么我们可以使用同样的解法,只是我们需要在队列中记录每个元素属于哪一行,而使用链表结构就避免了这种麻烦。…

最近总是Rank到很难的题目,这次遇到了LeetCode中通过率最低的题目。这道题目是一个图相关的问题,同时牵扯到很多坑,很多细节,即使思路正确稍不注意内存超出,时间超出都是常事儿,自己做出来还是需要废一番功夫的。博主写了BFS算法的大概就放弃了,后面翻了几份代码,找了个最简洁的 ,这里也只能讲解一下别人的代码了。…

        这道题很难想,主要有两种解法,一种是把这道题目转化成之前那道(#084)直方图面积计算的题目,使用栈来做,但是还有更优雅的方法,使用DP。这两种方法的时间复杂度都是O(mn),空间复杂度都是O(n)。…

Skyline是一个经典问题了,一开始博主思考先进行高度排序,从高到低来确定关键点。事实上通过优先队列来获取当前位置的最大高度,沿着x轴来遍历是最好的。这篇博客提供了一份19ms的答案,战胜了97%,当然是从讨论区淘出来的,博主没想到这么优秀的方法。…

这道题一种普遍的解法是动态规划。但是同样是动态规划,也有优劣之分。这篇博客贡献一份36ms(80%+)的答案,推荐这份答案不仅是因为速度,还是因为这种思路十分清晰,当然也可以参考讨论区中的7行的动态规划答案,也是十分优秀的。…