力扣---接雨水---单调队列

题目：

单调队列思想：

没有思路的小伙伴可以先把这个想清楚哦：力扣hot10---大根堆+双端队列-CSDN博客

从上面的图就可以发现，如果柱子呈递减序列，那么不会接到雨水，只要有一个小凸起柱子，那么这个柱子就会和之前的柱子接到雨水。所以我们维护一个递减序列，如果遍历到某个柱子接到雨水时，就把前面比他矮的柱子pop掉，同时因为接到了雨水，前面的柱子高度也会发生变化，变成了接完雨水后的最高值（height数组中的元素值需改变的原因为：考虑到后面还会有更高的柱子使得该柱子再次接到点雨水，我们需要改变柱子的长度）。一个柱子能接雨水的最大值该怎么求呢？首先，我们比较遍历到的这个柱子和队列中第一高的柱子哪个更低，如果该值为lower，那么接到的雨水部分英文lower-height[ i ]。不清晰的友友直接看代码吧~

代码：

C++：

class Solution {
public:int calculate(vector<int>& height,int idx_r,int idx_l){int s=0;int min_=min(height[idx_l],height[idx_r]);int r=height[idx_r];for(int i=idx_l;i<idx_r;i++){if(r>height[i]){s+=min_-height[i];height[i]=min_;}}return s;}int trap(vector<int>& height) {//单调队列（维护递减的序列）deque<pair<int,int>> q;int len=height.size();int s=0;for(int i=0;i<len;i++){//出while(!q.empty() and q.back().first<=height[i]){s+=calculate(height,i,q.front().second); //计算新加的面积大小，同时改变数组中的元素，因为已经接了雨水q.pop_back();}//进q.push_back({height[i],i});}return s;}
};

Python：

class Solution:def calculate(self,height:List[int],idx_r:int,idx_l:int) -> int:s=0min_=min(height[idx_l],height[idx_r])r=height[idx_r]for i in range(idx_l,idx_r):if r>height[i]:s+=min_-height[i]height[i]=min_return sdef trap(self, height: List[int]) -> int:q=deque()height_len=len(height)s=0for i in range(height_len):while q and q[-1][0]<=height[i]:s+=self.calculate(height,i,q[0][1])q.pop()q.append((height[i],i))return s

明天继续更新这道题的动态规划做法以及力扣hot--课程表