【算法练习Day50】下一个更大元素II接雨水

在这里插入图片描述

​📝个人主页:@Sherry的成长之路
🏠学习社区:Sherry的成长之路(个人社区)
📖专栏链接:练题
🎯长路漫漫浩浩,万事皆有期待

文章目录

  • 下一个更大元素II
  • 接雨水
    • 单调栈思路
  • 总结:

下一个更大元素II

503. 下一个更大元素 II - 力扣(LeetCode)
在这里插入图片描述

给定一个循环数组 nums ( nums[nums.length - 1] 的下一个元素是 nums[0] ),返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1 。

在遍历的过程中模拟走了两边nums。

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Stack<Integer> st = new Stack<>();
        int[] result = new int[nums.length];
        Arrays.fill(result, -1);

        st.push(0);
        for (int i = 1; i < 2 * nums.length; i++) {
            while (!st.isEmpty() && nums[i%nums.length] > nums[st.peek()]) {
                result[st.pop()] = nums[i % nums.length];
            }
            st.push(i % nums.length);
        }
        return result;
    }
}

接雨水

42. 接雨水 - 力扣(LeetCode)

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

单调栈思路

1.首先单调栈是按照行方向来计算雨水,如图:
在这里插入图片描述

在这种情况下,可以接6个单位的雨水

2.使用单调栈内元素的顺序

从大到小还是从小到大呢?

从栈头(元素从栈头弹出)到栈底的顺序应该是从小到大的顺序。

因为一旦发现添加的柱子高度大于栈头元素了,此时就出现凹槽了,栈头元素就是凹槽底部的柱子,栈头第二个元素就是凹槽左边的柱子,而添加的元素就是凹槽右边的柱子。

如图:

在这里插入图片描述

3.遇到相同高度的柱子怎么办。
遇到相同的元素,更新栈内下标,就是将栈里元素(旧下标)弹出,将新元素(新下标)加入栈中。

例如 5 5 1 3 这种情况。如果添加第二个5的时候就应该将第一个5的下标弹出,把第二个5添加到栈中。

因为我们要求宽度的时候 如果遇到相同高度的柱子,需要使用最右边的柱子来计算宽度。

如图所示:
在这里插入图片描述

4.栈里要保存什么数值
使用单调栈,也是通过 长 * 宽 来计算雨水面积的。

长就是通过柱子的高度来计算,宽是通过柱子之间的下标来计算,

其实不用,栈里就存放下标就行,想要知道对应的高度,通过height[stack.top()] 就知道弹出的下标对应的高度了。

Deque<Integer> stack = new LinkedList<>(); // 存着下标,计算的时候用下标对应的柱子高度

明确了如上几点,我们再来看处理逻辑。

以下逻辑主要就是三种情况

情况一:当前遍历的元素(柱子)高度小于栈顶元素的高度 height[i] < height[st.top()]
情况二:当前遍历的元素(柱子)高度等于栈顶元素的高度 height[i] == height[st.top()]
情况三:当前遍历的元素(柱子)高度大于栈顶元素的高度 height[i] > height[st.top()]

先将下标0的柱子加入到栈中,st.push(0);。 栈中存放我们遍历过的元素,所以先将下标0加进来。

然后开始从下标1开始遍历所有的柱子,for (int i = 1; i < height.size(); i++)。

如果当前遍历的元素(柱子)高度小于栈顶元素的高度,就把这个元素加入栈中,因为栈里本来就要保持从小到大的顺序(从栈头到栈底)。

if (height[i] < height[stack.peek()]) {
    stack.push(i);
}

如果当前遍历的元素(柱子)高度等于栈顶元素的高度,要跟更新栈顶元素,因为遇到相相同高度的柱子,需要使用最右边的柱子来计算宽度。

}else if (height[i] == height[stack.peek()]) {
    stack.pop();
    stack.push(i);
}

如果当前遍历的元素(柱子)高度大于栈顶元素的高度,此时就出现凹槽了
在这里插入图片描述

取栈顶元素,将栈顶元素弹出,这个就是凹槽的底部,也就是中间位置,下标记为mid,对应的高度为height[mid](就是图中的高度1)。

此时的栈顶元素st.top(),就是凹槽的左边位置,下标为st.top(),对应的高度为height[st.top()](就是图中的高度2)。

当前遍历的元素i,就是凹槽右边的位置,下标为i,对应的高度为height[i](就是图中的高度3)。

此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的元素,三个元素来接水!

那么雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度,代码为:int h = min(height[st.top()], height[i]) - height[mid];

雨水的宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1(因为只求中间宽度),代码为:int w = i - st.top() - 1 ;

当前凹槽雨水的体积就是:h * w。

class Solution {
    public int trap(int[] height) {
        Stack<Integer> st = new Stack<>();
        st.push(0);
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            while (!st.isEmpty() && height[i] > height[st.peek()]) {
                int mid = st.pop();
                if (!st.isEmpty()) {
                    int h = Math.min(height[st.peek()], height[i]) - height[mid];
                    int w = i - st.peek() - 1;
                    sum += h * w;
                }
            }
            st.push(i);
        }
        return sum;
    }
}

总结:

今天我们完成了下一个更大元素II、接雨水两道题,相关的思想需要多复习回顾。接下来,我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。

当然,本文仍有许多不足之处,欢迎各位小伙伴们随时私信交流、批评指正!我们下期见~

在这里插入图片描述

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

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

相关文章

Java毕业设计第90期-基于springboot的学习英语管理系统

获取源码资料&#xff0c;请移步从戎源码网&#xff1a;从戎源码网_专业的计算机毕业设计网站 项目介绍 基于springboot的学习英语管理系统&#xff1a;前端 thymeleaf、jquery&#xff0c;后端 maven、springmvc、spring、mybatis&#xff0c;角色分为管理员、用户&#xff…

小程序进阶学习(音乐首页-轮播图)

轮播图 样式 轮播图的重点是轮播图的大小&#xff0c;因为每个手机的屏幕大小不一样&#xff0c;但是轮播图的大小是固定的就需要一些技术获取到手机的轮播图大小&#xff0c;然后再设置图片的大小和轮播图边框的大小。 页面代码 <van-searchvalue"{{ value }}"s…

PID笔记

Improving the Beginner’s PID 参考资料 Improving the Beginner’s PID – Introduction The Beginner’s PID 以下是每个人第一次学习的PID方程&#xff1a; 这导致几乎每个人都编写了以下PID控制器&#xff1a; /*working variables*/ unsigned long lastTime; double…

【c++函数重载】

文章目录 一. 命名空间二 .全缺省参数和半缺省参数三 . 函数重载 一. 命名空间 1.不指定域&#xff1a;先在局部找&#xff0c;再全局。 2. 指定域&#xff1a;到指定的命名空间去找。 3. 当把指定命名空间放开时&#xff0c;即using namespace std&#xff1b;例如放开标准c库…

聊聊Java虚拟机(一)—— 类加载子系统

1. 前言 ​ 虚拟机就是一款用来执行虚拟计算机指令的计算机软件。它相当于一台虚拟计算机。大体上&#xff0c;虚拟机分为系统虚拟机和程序虚拟机。系统虚拟机就相当于一台物理电脑&#xff0c;里面可以安装操作系统&#xff1b;程序虚拟机是为了执行单个计算机程序而设计出来…

imgaug库图像增强指南(32):塑造【雪景】效果的视觉魔法

引言 在深度学习和计算机视觉的世界里&#xff0c;数据是模型训练的基石&#xff0c;其质量与数量直接影响着模型的性能。然而&#xff0c;获取大量高质量的标注数据往往需要耗费大量的时间和资源。正因如此&#xff0c;数据增强技术应运而生&#xff0c;成为了解决这一问题的…

蓝桥杯练习题(十二)

&#x1f4d1;前言 本文主要是【算法】——蓝桥杯练习题&#xff08;十二&#xff09;的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是听风与他&#x1f947; ☁️博客首页&#xff1a;CSDN主页听风与他…

【蓝桥杯日记】复盘篇一:深入浅出顺序结构

&#x1f680;前言 本期是一篇关于顺序结构的题目的复盘,通过复盘基础知识&#xff0c;进而把基础知识学习牢固&#xff01;通过例题而进行复习基础知识。 &#x1f6a9;目录 前言 1.字符三角形 分析&#xff1a; 知识点&#xff1a; 代码如下 2. 字母转换 题目分析: 知…

加固密码安全:保护您的个人信息

一、引言 在数字化时代&#xff0c;密码安全是保护个人信息和数据的重要环节。然而&#xff0c;许多人在创建和管理密码时存在一些常见的安全漏洞&#xff0c;如使用弱密码、重复使用密码等。本文将详细介绍密码安全的重要性&#xff0c;并提供一些有效的方法和技巧&#xff0…

使用DALL-E 3模型模拟AI女友的一天 |【人人都是算法专家】

Rocky Ding 公众号&#xff1a;WeThinkIn 知乎&#xff1a;Rocky Ding 写在前面 【人人都是算法专家】栏目专注于分享AI行业中业务/竞赛/研究/产品维度的思考与感悟。欢迎大家一起交流学习&#x1f4aa; 大家好&#xff0c;我是Rocky。 我们都知道DALL-E 3是和Stable Diffusio…

Windows ssh登录eNSP交换机

目录 1. Cloud IO配置1.1 创建UDP端口1.2 创建本地连接1.3 端口映射设置 2. 交换机配置2.1 配置vlanif2.2 配置vty2.3 配置ssh用户2.4 配置aaa2.5 使用Xshell工具登录2.6 用户和密码2.7 登录成功 3. 使用cmd 登录报错提示3.1 手动指定加密算法&#xff0c;提示密码长度无效3.2 …

自定义注解与拦截器实现不规范sql拦截(拦截器实现篇)

最近考虑myBatis中sql语句使用规范的问题&#xff0c;如果漏下条件或者写一些不规范语句会对程序性能造成很大影响。最好的方法就是利用代码进行限制&#xff0c;通过拦截器进行sql格式的判断在自测环节就能找到问题。写了个简单情景下的demo&#xff0c;并通过idea插件来将myB…

Twisted Circuit洛谷绿题题解

Twisted Circuit 题面翻译 读入四个整数 0 0 0 或者 1 1 1&#xff0c;作为如图所示的电路图的输入。请输出按照电路图运算后的结果。 感谢PC_DOS 提供的翻译 题目描述 输入格式 The input consists of four lines, each line containing a single digit 0 or 1. 输出格…

编译和链接详解

文章目录 前言翻译环境和运行环境翻译环境和运行环境图解 翻译环境编译预处理&#xff08;预编译&#xff09;阶段编译汇编 链接 运行环境总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 在软件开发的世界中&#xff0c;编译和链接是构建程序的两个…

【GitHub项目推荐-开源的任务管理工具】【转载】

推荐一个开源的任务管理工具&#xff0c;该工具会提供各类文档协作功能、在线思维导图、在线流程图、项目管理、任务分发、即时 IM&#xff0c;文件管理等等。该开源项目使用到 Vue、Element-UI、ECharts 等技术栈。 开源地址&#xff1a;www.github.com/kuaifan/dootask 预览地…

5G_系统同步机制(八)

BBU和RRU的同步机制 为什么要做到系统同步 在TDD模式下工作时&#xff0c;为了避免相邻小区之间的干扰&#xff0c;近距离的所有gNB在任何时间点都必须具有相同的传输方向(DL或UL)。这样做的必要条件是在BTS之间同步SFN (System Frame number)和time Slot。此外&#xff0c;由…

meshgrid contour contourf

meshgrid contour contourf 参考video: https://www.bilibili.com/video/BV1qW411A775/?spm_id_from333.337.search-card.all.click&vd_sourced171c31a396363b8ea8c0e92a59cee6b 官方文档: https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.contourf.html#ma…

嵌入式-C语言-江科大-数据类型宏定义#define关键字typedef结构体

这是C语言中高级相关知识&#xff0c;在单片机中实战的一些用法 参考C语言江科大视频的学习笔记&#xff0c;详细举例子并且完整记录up的想法&#xff0c;包括内容有c语言数据类型&宏定义#define&关键字typedef&结构体&预处理指令 文章目录 一:C语言数据类型二…

idea 折叠某段代码 这段特定某段代码

如何折叠IntelliJ IDEA代码片段_w3cschool ctrlALTT

HNU-数据挖掘-作业1

数据挖掘课程作业作业1 计科210X 甘晴void 202108010XXX 第一题 假设所分析的数据包括属性 age,它在数据元组中的值&#xff08;以递增序&#xff09;为13 ,15 ,16 ,16 ,19 ,20 ,20 ,21 ,22 ,22 ,25 ,25 ,25 ,25 ,30 ,33 ,33 ,35 ,35 ,35 ,35 ,36 ,40 ,45 ,46 ,52,70。 a.…