leetcode-42:接雨水

简介: leetcode-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

解题

参考链接

方法一:双指针(超时)

查找当前位置(比如索引4)左右的最大高度,左(索引3),右(索引7)

由于接水取决于两侧最小高度,那么h=min(lHeight,rHeight)-height[i];

class Solution {
public:
    int trap(vector<int>& height) {
        int res=0;
        for(int i=0;i<height.size();i++){
            if(i==0||i==height.size()-1) continue;
            int lHeight=height[i];
            int rHeight=height[i];
            for(int l=i-1;l>=0;l--){
                lHeight=max(lHeight,height[l]);
            }
            for(int r=i+1;r<height.size();r++){
                rHeight=max(rHeight,height[r]);
            }
            int h=min(lHeight,rHeight)-height[i];
            if(h>0) res+=h;
        }
        return res;
    }
};

方法二:动态规划

和方法一 一样的思想,只不过用两个数组记录了每个柱子的左边最大高度和右边最大高度

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        vector<int> maxLeft(n,0);
        vector<int> maxRight(n,0);
         // 记录每个柱子左边柱子最大高度
        maxLeft[0]=height[0];
        for(int i=1;i<n;i++){
            maxLeft[i]=max(height[i],maxLeft[i-1]);
        }
        // 记录每个柱子右边柱子最大高度
        maxRight[n-1]=height[n-1];
        for(int i=n-2;i>=0;i--){
            maxRight[i]=max(height[i],maxRight[i+1]);
        }
        // 求和
        int res=0;
        for(int i=0;i<n;i++){
            int h=min(maxLeft[i],maxRight[i])-height[i];
            if(h>0) res+=h;
        }
        return res;
    }
};

方法三:单调栈

利用单调栈,按照行计算

情况一:height[i] 入栈

情况二:height[i]==height[i-1] 将一样高度的先出栈,把最新的入栈 ,防止 按照行计算的时候重复计算

情况三:height[i]>height[i-1] 凹槽出现,按照行进行计算

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() <= 2) return 0; // 可以不加
        stack<int> st; // 存着下标,计算的时候用下标对应的柱子高度
        st.push(0);
        int sum = 0;
        for (int i = 1; i < height.size(); i++) {
            if (height[i] < height[st.top()]) {     // 情况一
                st.push(i);
            } if (height[i] == height[st.top()]) {  // 情况二
                st.pop(); // 其实这一句可以不加,效果是一样的,但处理相同的情况的思路却变了。
                st.push(i);
            } else {                                // 情况三
                while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是while
                    int mid = st.top();
                    st.pop();
                    if (!st.empty()) {
                        int h = min(height[st.top()], height[i]) - height[mid];
                        int w = i - st.top() - 1; // 注意减一,只求中间宽度
                        sum += h * w;
                    }
                }
                st.push(i);
            }
        }
        return sum;
    }
};

简洁的一种

参考链接

if (st.empty()) break;使得 最左侧不能装水

最后遍历完后stack依然不是空的,这样使得最右侧,不能装水

int trap(vector<int>& height)
{
    int ans = 0;
    stack<int> st;
    for (int i = 0; i < height.size(); i++)
    {
        while (!st.empty() && height[st.top()] < height[i])
        {
            int cur = st.top();
            st.pop();
            if (st.empty()) break;
            int l = st.top();
            int r = i;
            int h = min(height[r], height[l]) - height[cur];
            ans += (r - l - 1) * h;
        }
        st.push(i);
    }
    return ans;
}


相关文章
|
8月前
|
API C# vr&ar
C++在游戏开发中的统治地位——从引擎到游戏逻辑
当谈到游戏开发,C++是一个绕不开的名字。从AAA级大作到独立游戏,从游戏引擎到游戏逻辑,C++凭借其高性能、底层控制能力和跨平台特性,成为游戏工业的基石。本文将深入探讨C++在游戏开发各个层面的应用。
668 5
|
9月前
|
人工智能 弹性计算 运维
小白也能上手!阿里云推出 OpenClaw 极速简易部署方案
阿里云OpenClaw是开源本地优先AI智能体平台,支持邮件处理、周报生成、资料查询、代码编写等任务,数据全留本地,保障隐私。技术小白也能通过阿里云轻量服务器“一键部署”,几分钟即可拥有专属AI数字员工。
716 15
|
11月前
|
监控 安全 物联网
RFID医院资产管理新模式
RFID技术能实现医院资产的实时定位、自动盘点和高效追溯,大幅提升资产管理效率并降低运营成本。医院资产(如设备、药品、耗材)数量大、流动快,传统管理方式容易出现丢失、盘点耗时等问题,RFID恰好能解决这些核心痛点,RFID医院资产管理新模式。
|
人工智能 自然语言处理 数据可视化
实践教程|如何创建一个WhatsApp AI Chatbot
无需代码!使用阿里云百炼 + Chat App 消息服务,10 分钟创建 WhatsApp AI 聊天机器人,支持企业知识库问答
1541 0
|
Python
Python音频处理-图解傅里叶分析
傅里叶分析是一种将函数表示为周期成分之和的方法,并通过离散傅里叶变换(DFT)将信号从时域转换到频域,提取频率特征。通过快速傅里叶变换(FFT),我们可分析方波的主要频率成分,并利用这些成分重建波形,直观展示频率域对原始信号的影响。
508 0
|
JavaScript Linux iOS开发
Motrix:Star46.4k,有了这个开源项目你的烦恼基本少了一半?一款开源功能全面的下载管理器,用上它妈妈再也不用担心下载速度啦~~~
嗨,大家好,我是小华同学。今天为大家介绍一款全能下载管理器——Motrix。它支持HTTP、FTP、BitTorrent等多种协议,拥有简洁易用的界面和强大的下载功能,包括选择性下载、多线程加速、自动更新Tracker列表等,适用于工作、学习和娱乐场景。欢迎关注我们,获取更多优质开源项目和高效工具。
1476 15
Motrix:Star46.4k,有了这个开源项目你的烦恼基本少了一半?一款开源功能全面的下载管理器,用上它妈妈再也不用担心下载速度啦~~~
|
Python
使用python计算两个日期之前的相差天数,周数
使用python计算两个日期之前的相差天数,周数
1515 0
|
数据可视化 IDE 程序员
14 款超赞的代码片段生成工具😍(程序员必备)
在本文中,我将介绍 14 款代码片段图片生成器,每款工具都具备独特功能,能够满足不同需求,帮助你将代码转化为精美、易于分享的视觉内容。
1200 13
14 款超赞的代码片段生成工具😍(程序员必备)
|
人工智能 搜索推荐 算法
解决方案评测|主动式智能导购AI助手构建
阿里云的主动式智能导购AI助手是电商商家提升用户体验和销量的利器。它能实时分析用户行为,提供个性化推荐,支持多渠道无缝对接,并具备语音和文本交互功能。通过注册阿里云账号、开通服务、配置项目、设置推荐策略、集成到平台并测试优化,商家可以轻松部署这一工具。关键代码示例帮助理解API对接和数据处理。建议增强个性化推荐算法、优化交互体验并增加自定义选项,以进一步提升效果。
1299 11
|
SQL 数据库
DBeaver执行sql文件
本文介绍了DBeaver这款支持多种数据库的通用数据库管理工具和SQL客户端,它具备查看数据库结构、执行SQL查询和脚本、浏览和导出数据等功能。
5034 1
DBeaver执行sql文件