6.21
【思路-动规】接雨水-力扣
题目描述不贴了，在上面的链接里↑
第一遍写的思路过于简单，按每层遍历，还可以递归少写点代码。但时间复杂度O(n*n)，导致在复杂数据点超时。
参考了windliang的题解才想到可以按列遍历，每个柱子能储存的雨水只和左边所有柱子的最高lmax，与右边所有最高rmax有关。两者中的较小者min减去该柱子的高度h得到的结果和0相比的较大值就是答案。如果这个差小于等于0，就应该等于0。
进一步还可以用单调栈储存数据，使空间复杂度再次降低。（这里下次好好研究一下）
原文：https://www.cnblogs.com/Song-Meow/p/13174708.html