【Leetcode】接雨水(双指针、单调栈)

目录

💡题目描述

💡双指针解法

💡单调栈解法



💡题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

提示:

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

💡双指针解法

思路:

假设每个宽度为1的柱子那里有一个高度未知的宽度为1的水桶,这个水桶能接的水就是当前柱子所处位置能留下的雨水,而水桶的左边木板的高度取决于当前柱子左边所有的柱子中最高的那个柱子的高度水桶右边木板的高度取决于当前柱子右边所有的柱子中最高的柱子的高度而水桶左右木板中较小的那个木板的高度减去当前柱子的高度就是当前水桶能接到的水,也就是当前位置留下的雨水。

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        vector<int>pmax(n,0);
        vector<int>smax(n,0);
        pmax[0]=height[0];
        for(int i=1;i<n;i++)
        {
            pmax[i]=max(pmax[i-1],height[i]);//计算前缀最大值
        }
        smax[n-1]=height[n-1];
        for(int i=n-2;i>=0;i--)
        {
            smax[i]=max(height[i],smax[i+1]);//计算后缀最大值
        }
        int ans=0;
        for(int i=0;i<n;i++)
        {
            ans+=(min(pmax[i],smax[i])-height[i]);
        }
        return ans;
    }
};

时间复杂度:O(n)

空间复杂度:O(n)

优化:

上一个解法需要用到两个大小为n的数组分别记录前缀最大值和后缀最大值,而事实上我们可以在左右指针遍历的同时分别记录左边前缀最大值和右边后缀最大值,如果左边前缀最大值小于右边后缀最大值,那么可以计算左边所能接的雨水,计算方法和上面一样,这里就是左边木板高度较小,就可以直接减去柱子高度,否则,计算右边所能接的雨水,左右最大高度相等时随便计算哪一边都是可以的。

class Solution {
public:
    int trap(vector<int>& height) {
        /*假设有一个宽为1的水桶放在每一个柱子那里,高度未知
        每个水桶接的水的多少取决于当前柱子高度和
        它左右区间中分别的最大的柱子高度中较小的那个柱子高度之差,
        例如假设当前柱子高度为1,左边最大的柱子高度为3,右边最大柱子高度为2,
        当前柱子这里的水桶能接的水量为(2-1)=1*/
        int n=height.size();
        int pmax=0;
        int smax=0;
        int l=0;
        int r=n-1;
        int ans=0;
        int i=0;
        while(l<r)
        {
            pmax=max(pmax,height[l]);
            smax=max(smax,height[r]);
            if(pmax<smax)
            {
            ans+=pmax-height[l];
            l++;
            }
            else
            {
                ans+=smax-height[r];
                r--;
            }
        }
        return ans;
    }
};

💡单调栈解法

思路:

这个方法的思路就是求每个凹槽的面积,即横向求解(上一个方法是纵向求解),要得到凹槽的面积,就要求出当前柱子左右两边第一个比它高的柱子,想到这里,就会发现其实很适合用单调栈的方法来求解。

对于这个单调栈,到底是用递增栈还是递减栈呢?

由于我们是要找到当前柱子左右两边第一个比它高的柱子,当我们没有找到比它高的柱子的时候,是会把这个柱子的高度入栈的,一旦发现添加的柱子高度大于栈顶元素了,此时就出现凹槽了,栈顶元素就是凹槽底部的柱子,栈顶第二个元素就是凹槽左边的柱子,而添加的元素就是凹槽右边的柱子。而遇到相同元素时,可以更新栈内元素,也可以选择不处理。

栈内是存储柱子的高度还是下标呢?

这里选择存下标,因为我们要求的是面积,存下标既可以得到凹槽的宽度,也可以得到凹槽的高度,而凹槽的高度是这个柱子左右两边第一个比它高的柱子的高度中较小的那一个减去它的高度,

对于栈顶元素和当前柱子的高度主要有三种情况:

  • 情况一:当前遍历的元素(柱子)高度小于栈顶元素的高度 height[i] < height[st.top()],此时选择入栈。
  • 情况二:当前遍历的元素(柱子)高度等于栈顶元素的高度 height[i] == height[st.top()],此时可以选择更新栈内元素的下标。
  • 情况三:当前遍历的元素(柱子)高度大于栈顶元素的高度 height[i] > height[st.top()],此时就出现凹槽了,计算凹槽面积。

可以发现栈顶和栈顶的下一个元素以及要入栈的元素,这三个元素来接雨水!

具体代码:

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        stack<int>st;//单调递增栈
        st.push(0);
        int sum=0;
        for(int i=1;i<n;i++)
        {
            if(height[i]<height[st.top()])
            {
                st.push(i);
            }
            else if(height[i]==height[st.top()])
            {
                st.pop();
                st.push(i);//更新相同高度柱子的下标
            }
            else
            {
                while(!st.empty()&&height[i]>height[st.top()])
                {
                    int mid=st.top();
                    st.pop();
                    if(!st.empty())
                    {
                        int l=min(height[st.top()],height[i])-height[mid];
                        int w=i-st.top()-1;
                        sum+=l*w;
                    }
                }
            }
            st.push(i);
        }
        return sum;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/338019.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

this.$set的用法

作用&#xff1a; 在data里面绑定的数据具有响应式的效果,也就是我们说的V-Model 数据更新视图,视图也能更新数据&#xff0c;如果不是data里面的数据如何添加响应式呢&#xff1f; this.$Set这个方法能够实现 用法&#xff1a; this.$Set(要添加的对象,要添加的属性’,要添…

为什么C++17要引入std::string_view?

目录 1.引言 2.原理分析 2.1.结构 2.2.构造函数 2.3.成员函数 2.4.std::string_view字面量 3.实例 3.1.std::string_view和std::string的运算符操作 3.2.查找函数使用 3.3.std::string_view和临时字符串 4.总结 1.引言 在C/C日常编程中&#xff0c;我们常进行数据的…

Offer必备算法_双指针_八道力扣OJ题详解(由浅到深)

目录 双指针算法原理 ①力扣283. 移动零 解析代码 ②力扣1089. 复写零 解析代码 ③力扣202. 快乐数 解析代码 ④力扣11. 盛最多水的容器 解析代码 ⑤力扣611. 有效三角形的个数 解析代码 ⑥剑指 Offer 57. 和为s的两个数字 解析代码&#xff1a; ⑦力扣15. 三数之…

最通俗易懂的JVM内存管理与对象创建原理

前言 对于Java程序员来说&#xff0c;在虚拟机自动内存管理机制的帮助下&#xff0c;不再需要像 C/C程序为每一个new操作去写配对 的delete/free代码&#xff0c;不容易出现内存泄漏和内存溢出问题。也正是因为Java程序员把控制内存的权力交给了Java虚拟机&#xff0c;一旦出现…

SpringMVC基础知识学习笔记

Universe Infinity Inc. 目录 一、学习SpringMVC主要是学什么1、SpringMVC的基本原理2、SpringMVC学习串联 二、快速体验SpringMVC的开发1、新建项目&#xff0c;转成web项目2、引入依赖3、编写Spring的配置类4、配置web启动类&#xff0c;替代web.xml5、编写Handler&#xff…

都在卷鸿蒙开发,那就推荐 几个鸿蒙开源项目

如果要问2024年最火的技术是什么,那鸿蒙开发必须占据一些位置,HarmonyOS是华为自主研发的物联网操作系统,自2019年8月正式发布以来便受到了广大开发者的追崇。为了方便大家学习鸿蒙开发,本文分享 12 个开源的鸿蒙实战项目,希望能从这些项目中获得启发和实用经验。 小狐浏…

IDEA的database使用

一、数据据库 在使用database之前&#xff0c;首先你的电脑要安装好了数据库并且启动。 MySQL卸载手册 链接&#xff1a;https://pan.baidu.com/doc/share/AVXW5SG6T76puBOWnPegmw-602323264797863 提取码&#xff1a;hlgf MySQL安装图解 链接&#xff1a;https://pan.baidu.…

Win10/11中VMware Workstation设置网络桥接模式

文章目录 一、添加VMware Bridge Protocol服务二、配置桥接参数1.启用系统Device Install Service服务2.配置VMware 需要确认物理网卡是否有添加VMware Bridge Protocol服务 添加VMware Bridge Protocol服务 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参…

艾比森的“增长炼金术”:从四力驱动到三层面增长

在技术驱动的LED显示行业&#xff0c;产品迭代快、周期波动大&#xff0c;企业经营时时承压。 但是&#xff0c;市场上总不乏打破“传统”的个例。根据2023年业绩预告&#xff0c;艾比森预计2023年实现归母净利润3.10亿-3.50亿元&#xff0c;同比增长52.70%-72.40%&#xff1b…

HttpServletRequest getServerPort()、getLocalPort() 、getRemotePort() 区别

getRemotePort() 、getServerPort()、getLocalPort() request.getServerPort()、request.getLocalPort() 和 request.getRemotePort() 这三个方法都是获取与HTTP请求相关的端口信息的 客户端(如浏览器)通过某个随机分配的网络连接端口(7070) 向服务器发送HTTP请求( http://exam…

【Docker】未来已来 | Docker技术在云计算、边缘计算领域的应用前景

欢迎来到英杰社区&#xff1a; https://bbs.csdn.net/topics/617804998 欢迎来到阿Q社区&#xff1a; https://bbs.csdn.net/topics/617897397 &#x1f4d5;作者简介&#xff1a;热爱跑步的恒川&#xff0c;致力于C/C、Java、Python等多编程语言&#xff0c;热爱跑步&#xff…

[小程序]向服务器上传图片和从服务器下载图片

本例的服务器基于flask&#xff0c;配置flask可以参见[Flask]上传多个文件到服务器https://blog.csdn.net/weixin_37878740/article/details/128435136?ops_request_misc%257B%2522request%255Fid%2522%253A%2522170581653516800185854860%2522%252C%2522scm%2522%253A%252220…

【iOS】UICollectionView的基本使用

使用UITableView作为表格来展示数据完全没有问题&#xff0c;但仍有许多局限性&#xff0c;对于一些更加复杂的布局样式&#xff0c;就有些力不从心了 比如&#xff0c;UITableView只允许表格每一行只能显示一个cell&#xff0c;而不能在一行中显示多个cell&#xff0c;对于这…

项目管理该考哪个证书❓NPDP还是软考❓

有小伙伴在纠结是要考NPDP认证呢还是考软考呢❓ 今天小编要给大家好好说说NPDP认证❗️ &#x1f4a1;NPDP全称New Product Development Professional&#xff0c;也就是产品经理国际资格认证。 &#x1f525;NPDP是国际公认的为一的新产品开发专业认证&#xff0c;是集理论、方…

【神经网络】火箭点火发射-诠释一场数据与学习的奇妙之旅

火箭点火发射来理解神经网络的故事细节 在一个充满科技气息的研究室里&#xff0c;一群科学家们正在忙碌地准备着一次重要的火箭点火发射。这次发射不仅是一次航天探索的壮丽征程&#xff0c;更是一场利用神经网络处理数据的智慧之旅。 在火箭发射的背后&#xff0c;神经网络…

使用freessl为网站获取https证书及配置详细步骤

文章目录 一、进入freessl网站二、修改域名解析记录三、创建证书四、配置证书五、服务启动 一、进入freessl网站 首先进入freessl网站&#xff0c;需要注册一个账号 freessl网站 进入网站后填写自己的域名 接下来要求进行DCV配置 二、修改域名解析记录 到域名管理处编辑域名…

MySQL基础笔记(8)多表查询

一.多表关系介绍 项目开发中&#xff0c;在进行数据库表结构设计时&#xff0c;会根据业务需求及业务模块之间的关系&#xff0c;分析并设计表结构&#xff0c;由于业务之间相互关联&#xff0c;所以各个表结构之间也会存在着各种联系&#xff0c;分为如下3类&#xff1a; 一对…

【算法详解】力扣162.寻找峰值

​ 目录 一、题目描述二、思路分析 一、题目描述 力扣链接&#xff1a;力扣162.寻找峰值 峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums&#xff0c;找到峰值元素并返回其索引。数组可能包含多个峰值&#xff0c;在这种情况下&#xff0c;返回 任何一个…

Vulnhub靶机:FunBox 2

一、介绍 运行环境&#xff1a;Virtualbox 攻击机&#xff1a;kali&#xff08;10.0.2.15&#xff09; 靶机&#xff1a;FunBox 2&#xff08;10.0.2.27&#xff09; 目标&#xff1a;获取靶机root权限和flag 靶机下载地址&#xff1a;https://download.vulnhub.com/funbo…

【LeetCode每日一题】2788. 按分隔符拆分字符串

2024-1-20 文章目录 [2788. 按分隔符拆分字符串](https://leetcode.cn/problems/split-strings-by-separator/)思路&#xff1a; 2788. 按分隔符拆分字符串 思路&#xff1a; 对于每个单词&#xff0c;使用一个可变字符串 StringBuilder 来构建拆分后的单词。初始时&#xff0…