接雨水

题目 接雨水

思路分析

用单调栈找每个障碍物左边第一个比它高的位置，累加两障碍物之间的储雨量

两障碍物间雨水容量 = 左边障碍物与水面高度差 * 两障碍物距离

很抽象 要现想感觉不可能……

还可以用双指针

• 接雨水

1. 使用两个指针left和right分别从数组的左侧和右侧开始遍历，使用left_max和right_max来记录遍历过程中遇到的最高的墙高度。
2. 当left小于right时，计算当前水平面water_level，即left_max和right_max中的较小值。
3. 如果height[left]小于等于water_level，则在位置left可以积水，积水量为water_level - height[left]，然后left向右移动。
4. 类似地，如果height[right]小于等于water_level，则在位置right可以积水，积水量为water_level - height[right]，然后right向左移动。
5. 如果当前位置的高度大于water_level，则更新left_max或right_max为当前位置的高度，并移动对应的指针。
6. 当left和right相遇时，结束遍历。返回累积的积水总量。

代码实现

单调栈

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int h[N],s[N];
int n;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>h[i];

    int res=0,top=-1;
    for(int i=0;i<n;i++){
        int water=0;//记录水面高度
        while(top>=0 && h[s[top]]<=h[i]){
            res+=(h[s[top]]-water)*(i-s[top]-1);
            water=h[s[top]];
            top--;
        }
        //前面考虑的都是左边为水位限制的情况
        //如果一直递减 那就是当前位置为限制水位的关键
        if(top>=0)
            res+=(h[i]-water)*(i-s[top]-1);
        s[++top]=i;
    }
    cout<<res<<endl;
    return 0;
}

双指针

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int height[N];
int n;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>height[i];

    int ans=0;
    int left_max=0,right_max=0;
    int left=0,right=n-1;
    while(left<right){
        // 计算当前水位，即左侧和右侧最大高度的较小者
        int water_level=min(left_max,right_max);
        // 如果左侧的高度小于或等于水位
        if(height[left]<=water_level){
            // 计算当前位置可以接的雨水量，并累加到ans
            ans+=water_level - height[left];
            left++;
            continue;
        }
        // 如果右侧的高度小于或等于水位
        if(height[right]<=water_level){
            // 计算当前位置可以接的雨水量，并累加到ans
            ans+=water_level - height[right];
            right--;
            continue;
        }
        left_max=max(left_max,height[left]);// 更新左侧的最大高度
        right_max=max(right_max,height[right]);// 更新右侧的最大高度
    }
    cout<<ans<<endl;
    return 0;
}

同类题型

视频讲解

⬅️ 找出数组中的第一个回文字符串 🏠 00-刷题理模型 ➡️ 有序数组的平方