42 接雨水

题目给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。示例 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 个单位的雨水蓝色部分表示雨水。示例 2输入height [4,2,0,3,2,5]输出9思路接雨水只看当前位置的左右两边最长的柱子是否能组成水槽。如果从左往右遍历那么只需要看是否在当前位置的左边是否有一个更短的柱子以及一个更长的柱子组成水槽。因此可以考虑使用单调栈维护一个单调栈从上到下依次递增。从左到右依次遍历数组检查栈顶的元素是否小于当前的元素\qquad如果小于那么保存栈顶元素并弹出查看栈的下一个元素是否存在\qquad \qquad如果存在说明可以组成水槽水槽存水量为 min当前元素当前栈顶元素-弹出的栈顶元素∗ *∗当前元素序列-当前栈顶元素序列-1即水槽高度∗ *∗水槽宽度\qquad \qquad如果不存在那么说明两个柱子相邻,返回继续维护单调栈\qquad如果不小于或者栈为空把当前元素压入栈中最后返回结果用语言讲容易绕晕还是应该拿图或者过程来看点我看题解的方法二有动图代码class Solution{public: int trap(vectorintheight){// 维护一个从上到下递减的单调栈从左到右遍历height stackintstk;intnumsheight.size();intres0;for(inti0;inums;i){intcurr0;// 假设栈中有数据那么如果栈顶的元素小于i说明可能有水可以接 while(!stk.empty()height[stk.top()]height[i]){// 用一个数据存储栈顶元素,然后弹出,得到下面一个元素currheight[stk.top()];stk.pop();// 如果此时栈还不为空,说明两个柱子不相邻,可以接水 if(!stk.empty()){// 两个柱子接水的大小为:(左右两块柱子较小的-存储的柱子长度)*左右两个柱子的序列差-1,因为两个柱子各占了一个序列res(min(height[i],height[stk.top()])-curr)*(i-stk.top()-1);}}// 然后将柱子压入栈中作为可能的水槽 stk.push(i);}returnres;}};这种题目比较考验逻辑希望下次再做的时候能够回忆起来现在的思路。感谢 灵茶山艾府 基础算法精讲