[LeetCode]Trapping Rain Water II

不是很有思路的题目。之前的想法是模拟从最外一圈格子开始倒水，直到水没有办法留存下来，但是这样做的话时间复杂度太高。DP的思路的话，一个格子的存水量是取决于四周的格子，所以肯定是应该从外向内DP，但是具体遵循什么样的DP 公式却不好推导出来。看了别人的解答，才发现确实是很不错的解法。我们的思路是从外向内DP，那么存水量是取决于最短的那一块板子。我们从最外层的格子的集合s开始，我们每一次取最短的格子b出来，然后算它四周格子x的存水量，因为x的存水量就由b决定了。因为我们有一个不变的事实是，所有在s上和之前在s上的格子一直都会围城一个圈，而这个圈的存水高度就由当前的b（组成圈的格子不一样的情况下，b的高度很显然也不一样）决定，画个图会很好理解。之后更新x格子存水的高度，然后将x插入s，假设x高度小于b大么它的高度应该更新为b，因为剩下格子的存水高度不会小于b了，如果大于b，那么x高度不变。一直循环直到s为空，最后算出总存水量，时间复杂度O(n * log n)，n是格子总数，空间复杂度O(n)，代码如下：