本文转载自微信公众号《高性能架构探索》，作者于乐。转载本文请联系高性能架构探索公众号。今年，北京下了很多雨，淅淅沥沥地下着。整个中秋节的前两天都是在雨中度过的，没有往年中秋节的欢乐气氛。好在中秋节那天，天气晴朗，也算是给整个假期画上了一个圆满的句号。听着淅淅沥沥的雨声，想起前段时间在麦麦上看过一个帖子。阿里P8去面试某贴，算法挂在一边。而我3年前面试某家公司的时候，也是落在了同一个算法上。俗话说吃坑出智慧，重新整理了算法题，分享给大家，希望有用。接收雨水给定n个非负整数代表每列宽度为1的高度图，计算下雨后这样排列的列能接收多少雨水。雨水输入：height=[0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面由数组[0,1,0,2,1,0,1,3,2,1,2,1]表示高度图。在这种情况下，它可以接收6个单位的雨水（蓝色部分代表雨水）。乍一看标题，感觉很简单，却又不知从何说起。下面我们将循序渐进的分析这个问题的解决方法。暴力解一看到问题，出于思维定势，一定要找到“凹”槽的最低处，然后。..等等，越来越大，直到我放弃。我们不妨换个思路，每根柱子上可以放多少雨水。那么如何计算每根柱子上的雨水高度呢？它是左右支柱的最大高度与其高度之间的较小者的差值。文字上很难理解，但是大家用图片更容易理解。接下来，我们将计算列坐标（3）-（7），即红色框中所含的水量。我们先定义4个变量：res总水量，初始化为0height当前列的高度left_max左边最大高度（包括当前列本身）right_max右边最大高度（包括自身）,计算第(3)列处的水容量左侧最大高度left_max为2，右侧最大高度right_max为3，则横坐标3处的水量为min(left_max,right_max)-高度赋值后为min(2,3)-2，答案为0，即表示柱子(3)的水容量为0。那么我们计算柱子(4)的水容量.根据以上计算规则，左边最大高度为2，右边最大高度为3，则第(4)列的水容量为min(2,3)-1，答案为1.然后计算立柱（5）处的持水量。根据以上计算规则，左边最大高度为2，右边最大高度为3，则柱子（5）的持水量为min(2,3)-0，则答案为2。然后计算支柱（6）处的持水量。根据上述计算规则，左边最大高度为2，右边最大高度为3，则支柱（6）的持水量为min(2,3)-1，则答案为1。最后，计算支柱（7）处的水容量。左边的最大高度是3，右边的最大高度是3。那么柱子（7）的水容量是min(3,3)-3，也就是0。因此，柱子（3）to柱子之间的含水量(7)res=0+1+2+1+0=4代码实现1：inttrap(vector&height){intres=0;for(intcur=0;cur&height){intres=0;for(intcur=0;curheight[cur]){//需要判断res+=mx-height[cur];}}returnres;}蛮力解法简单易懂，时间复杂度为O(n2)。提交之后，毫无疑问就是TLE了。接下来，我们将从其他方面优化暴力破解方法。为了便于理解，下面的实现会使用实现二的思路。动态规划看过暴力法的实现，基本思路已经有了。它的时间复杂度是O(n2)，时间主要消耗在求两边柱子的最大高度上。那么有什么办法可以通过遍历一个常数的次数，得到所有列两边的高度呢？我们仍然以height=[0,1,0,2,1,0,1,3,2,1,2,1]为例计算双边最大值。左边最大值定义了数组left_max，其中left_max[i]编码了第i列的最大左边高度。我们来计算左边柱子的最大高度：Pillar(0),左边最大高度为0（左边没有柱子）Pillar(1),左边最大高度为0（左侧只有第0列）Pillar(2)，左侧最大高度为1（[01]数组的最大值）第(3)列，左侧最大高度为1(数组[010]的最大值)第(4)列，左边最大高度2([0102]数组的最大值)第(5)列，最大高度左边的最大为2([01021]数组的最大值)第(6)列，左边的最大高度为2([010210]数组的最大值)第(7)列，左边最大高度为2([0102101]数组的最大值)第(8)列，左边最大高度为3([01021013]数组的最大值)柱子(9),左侧最大高度为3([010210132]数组的最大值)柱子(10),左侧最大高度为3([0102101321]数组最大值)列(11),左侧最大高度为3([01021013212]arraymaxvalue)leftmaxvalue从上面的规则，我们分析发现有一定的规律可循，就是左边最大高度当前列为max（上一列左边的最大高度，上一列的高度）。代码表示如下：std::vectorleft_max(height.size(),0);for(inti=1;ileft_max(height.size(),0);intmx=0;for(inti=0;i&height){intres=0;std::vectorleft_max(height.size());std::vectorright_max(height.size());intmx=0;//循环1，计算左边的最大值for(inti=0;i=0;--i){right_max[i]=mx;mx=std::max(mx,height[i]);}//循环三，计算含雨水量for(inti=0;iheight[i]){res+=mn-高度[i];}}returnres;}以上代码相比暴力法优化后，时间复杂度优化为O(n)。作为一个c++coder，这是无法忍受的。可以优化吗？我们看到循环3纯粹是为了计算降雨量。loop2和loop3可以结合起来优化空间复杂度吗？一定是可以的，为了阅读方便，我们实现代码如下：inttrap(vector&height){intres=0;std::vectorv(height.size());intmx=0;//循环1，计算左边的最大值for(inti=0;i=0;--i){intmn=std::min(mx,v[i]);mx=std::max(mx,height[i]);if(mn>height[i]){res+=mn-height[i];}}returnres;}优化动态规划双指针动态规划方法，时间复杂度和空间复杂度都是O(n)，下面我们介绍一种只有一次循环，空间复杂度为O(1)的算法，就是双指针算法。雨水接收算法的核心思想是计算当前列的持水量，即左右两侧最大值中较小者与当前列的差值。我们先找到数组双端列中较小的值，然后将两边的列与这个较小的值进行比较。如果较小的值是左列，则左列向右移动，直到大于当前最小值。相反，如果较小的值是右列，则右列向左移动，直到它大于当前值。左右指针分别指向数组的第一个和最后一个位置，从两边向中间扫描。在当前两个指针确定的范围内，先比较两端，找出较小的值。如果较小的值是left指向的值，则从左边扫描向右扫描，如果较小的值是right指向的值，则从右向左扫描，如果遇到的值小于较小的值,将差值存储在结果中，如果遇到的值较大，则重新确定新的窗口范围，以此类推，直到左右指针重合inttrap(vector&height){intres=0;intleft=0;intright=height.size()-1;while(left0），会出栈，持水增量((min(1,1)-0)*(6-4)会同时计算-1)），增量为1，此时res=1+1=2。下标6指向的值等于栈顶(1=1)指向的值，当下标6入栈时，下标指向7，其值大于栈顶的值(3>1)，则栈顶出栈，计算增量为((min(3,1)-1)*(7-4-1))，增量为0，此时res=1+1+0=2此时下标还是7，栈顶的值为4。由于当前下标指向的值大于栈顶指向的值，弹出栈并计算持水增量((min(3,2)-1)*(7-3-1))。增量为3。此时res=1+1+0+3=5，计算增量水容量。此时栈中只有下标3，且其指向的值小于当前下标值（2<3），则将下标3出栈。此时栈为空，则下标7入栈，下标8指向小于栈顶指向的值（2<3），下标8入栈，下标9指向的值小于栈顶指向的值(1<2)。当下标9入栈时，下标为10，其对应的值大于栈顶指向的值（2>1），则出栈顶，计算increment((min(2,2)-1)*(10-8-1))，增量为1，此时res=1+1+0+3+1=6指向的值下标10小于栈顶值，将下标11指向的值压入栈中。至此，数组的循环结束，虽然栈中还有数字，坐标为781011，指向的值为3221，但是已经不能形成盛水的凹槽了，所以算法执行结束。代码实现如下：inttrap(vector&height){stackst;inti=0,res=0,n=height.size();while(i
