贵阳网站开发公司,中国域名管理中心,网站建设公司实力,云南汽车网络营销题目#xff1a; 单调队列思想#xff1a; 没有思路的小伙伴可以先把这个想清楚哦#xff1a;力扣hot10---大根堆双端队列-CSDN博客 从上面的图就可以发现#xff0c;如果柱子呈递减序列#xff0c;那么不会接到雨水#xff0c;只要有一个小凸起柱子#xff0c;那么这个…题目 单调队列思想 没有思路的小伙伴可以先把这个想清楚哦力扣hot10---大根堆双端队列-CSDN博客 从上面的图就可以发现如果柱子呈递减序列那么不会接到雨水只要有一个小凸起柱子那么这个柱子就会和之前的柱子接到雨水。所以我们维护一个递减序列如果遍历到某个柱子接到雨水时就把前面比他矮的柱子pop掉同时因为接到了雨水前面的柱子高度也会发生变化变成了接完雨水后的最高值height数组中的元素值需改变的原因为考虑到后面还会有更高的柱子使得该柱子再次接到点雨水我们需要改变柱子的长度。一个柱子能接雨水的最大值该怎么求呢首先我们比较遍历到的这个柱子和队列中第一高的柱子哪个更低如果该值为lower那么接到的雨水部分英文lower-height[ i ]。不清晰的友友直接看代码吧~ 代码
C
class Solution {
public:int calculate(vectorint height,int idx_r,int idx_l){int s0;int min_min(height[idx_l],height[idx_r]);int rheight[idx_r];for(int iidx_l;iidx_r;i){if(rheight[i]){smin_-height[i];height[i]min_;}}return s;}int trap(vectorint height) {//单调队列维护递减的序列dequepairint,int q;int lenheight.size();int s0;for(int i0;ilen;i){//出while(!q.empty() and q.back().firstheight[i]){scalculate(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:s0min_min(height[idx_l],height[idx_r])rheight[idx_r]for i in range(idx_l,idx_r):if rheight[i]:smin_-height[i]height[i]min_return sdef trap(self, height: List[int]) - int:qdeque()height_lenlen(height)s0for i in range(height_len):while q and q[-1][0]height[i]:sself.calculate(height,i,q[0][1])q.pop()q.append((height[i],i))return s明天继续更新这道题的动态规划做法以及力扣hot--课程表
