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

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

寻找K个最大组合,博主最开始使用BFS来做的,算法复杂度\(O(mn)\),计算和\(mn\),广度优先搜索\(V+E = mn+(m-1)(n-1)\),速度13ms。此外,博主对DP的掌握一直不够熟练,顺便贴了另一种使用DP的搜索方法,也是13ms,其实两种思路是差不多的。…

        一道很有意思的题目,题目是计算容器雨水积累量,实际上是利用广度优先搜索来不断收缩边界,计算雨水的积累。由于博主之前图一类的题目接触的比较少,这道题目看了一眼答案。这篇博客除了介绍这道题目本身,还将介绍stl中的优先队列priority queue,优先队列是广度优先搜索(BFS)必要的辅助。作为编程辅助,后面还顺便介绍了C++11的花括弧初始化。…