职业院校专题建设网站,江西省建设职业培训学校网站,长沙哪里可以做网站,万年历网站做题目#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动态规划思想
题解说是直觉然后用动态规划来优化我是真没有这直觉呀...
初始想法写到代码里面啦这里再贴一遍 初始想法对于每个height[i]所接的雨水量等于该柱子左面的所有柱子高度最大值以及 该柱子右面的所有柱子高度最大值这两个值取较小的那一个并减去该柱子原有的高度。 代码如下直觉版
class Solution {
public:int trap(vectorint height) {//初始想法对于每个height[i]所接的雨水量等于该柱子左面的所有柱子高度最大值以及//该柱子右面的所有柱子高度最大值这两个值取较小的那一个并减去该柱子原有的高度int lenheight.size();int res0;for(int i0;ilen;i){int maxl0;int maxr0;for(int j0;ji;j){maxlmax(maxl,height[j]);}for(int ji1;jlen;j){maxrmax(maxr,height[j]);}int tempmin(maxl,maxr)-height[i];if(temp0){restemp;}}return res;}
};
但是有一个点是过不去的那么我们继续用动态规划思想来优化。 既然代码中有这样一个过程是不是感觉有很多地方做了无用功为什么遍历每一个height[i]时都要计算左右的最大值呢不能一次性记录嘛感觉有点前缀和思想
for(int i0;ilen;i){int maxl0;int maxr0;for(int j0;ji;j){maxlmax(maxl,height[j]);}for(int ji1;jlen;j){maxrmax(maxr,height[j]);}
}
代码如下动态规划版
C
class Solution {
public:int trap(vectorint height) {//初始想法对于每个height[i]所接的雨水量等于该柱子左面的所有柱子高度最大值以及//该柱子右面的所有柱子高度最大值这两个值取较小的那一个并减去该柱子原有的高度int lenheight.size();int res0;vectorint maxl(len,0);vectorint maxr(len,0);for(int i1;ilen;i){maxl[i]max(maxl[i-1],height[i-1]);}for(int ilen-2;i0;i--){maxr[i]max(maxr[i1],height[i1]);}for(int i0;ilen;i){int tempmin(maxl[i],maxr[i])-height[i];if(temp0){restemp;}}return res;}
};
Python
class Solution:def trap(self, height: List[int]) - int:len_heightlen(height)res0maxl[0]*len_heightmaxr[0]*len_heightfor i in range(1,len_height):maxl[i]max(maxl[i-1],height[i-1])for i in range(len_height-2,-1,-1):maxr[i]max(maxr[i1],height[i1])for i in range(len_height):tempmin(maxl[i],maxr[i])-height[i]if temp0:restempreturn res
双指针思路
感觉题解说的有点迷没太看懂 先借用一下题解中的图 首先我们先来看第一张图由 i 和 j 两个指针因为height[ j ]height[ i ]所以 i 和 i 的右侧直到 j 都可以接到雨水右侧图片同理。有没有一点眼熟把两个指针放到两侧那个高度小于对方高度了就像中间移动。有点像这道题力扣---接雨水---单调队列-CSDN博客 我们还是看左面这张图我们将指针 i 左侧的最高柱子高度记为MaxLeft将指针 j 右侧的最高柱子高度记为MaxRight我们就可以得到柱子 i 接到的雨水MaxLeft-height[ i ]。为什么就确定柱子 i 左侧的最大值一定小于右侧的最大值呢右侧已经出现了一个较大的柱子 j 了如果height[ i ]height[ j ]那么说明 j 柱子是可以接到雨水的那么 i 指针也不会向右移动反而是 j 指针向左移动所以如果柱子 i 左侧的最大值大于右侧的最大值的话我们应该计算的是柱子 j 接到的雨水了MaxRight-height[ j ]因为左侧柱子已经足够高很绕很绕很绕。。。 代码如下
class Solution {
public:int trap(vectorint height) {//初始想法对于每个height[i]所接的雨水量等于该柱子左面的所有柱子高度最大值以及//该柱子右面的所有柱子高度最大值这两个值取较小的那一个并减去该柱子原有的高度int lenheight.size();int res0;int MaxLeft0;int MaxRight0;int left0;int rightlen-1;while(leftright){MaxLeftmax(MaxLeft,height[left]);MaxRightmax(MaxRight,height[right]);if(height[left]height[right]){resMaxLeft-height[left];left;}else{resMaxRight-height[right];right--;}}return res;}
};
Python代码和C类似就不附啦~
