代码随想录 Day50 单调栈 LeetCodeT503 下一个最大元素II T42接雨水

前言

前面我们说到了单调栈的第一题,下一个最大元素I,其实今天的两道题都是对他的变种,知道第一个单调栈的思想能够想清楚,其实这道题是很简单的

考虑好三个状态,大于等于小于,其实对于前面这些题目只要细心的小伙伴就会发现其实小于和等于的处理是一样的都是直接入栈,只有大于的才会将栈头一直出栈,最后将该元素入栈.

LeetCode T503 下一个最大元素II

题目链接:503. 下一个更大元素 II - 力扣(LeetCode)

题目思路:

这题的题目思路其实和上一题差不多,都是单调栈的经典例题,这题其实也就是在上一题的基础上加上了可以循环地搜索,其实我们只需要遍历两次数组即可,第一次的最大元素在单调栈

中保存了,第二次再遍历的时候就能达到循环搜索的效果了

这里贴上昨天单调栈的原版的思路链接:

代码和思路基本一样,这里不做过多赘述

代码随想录 Day49 单调栈01 LeetCode LeetCodeT739每日温度 T496 下一个最大元素I-CSDN博客

题目代码:

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];
        Arrays.fill(res,-1);
        Stack<Integer> st = new Stack<>();
        st.push(0);
        for(int i = 0;i<2*nums.length;i++){
            int k = i%nums.length;
            if(nums[k]<=nums[st.peek()]){
                st.push(k);
            }else{
                while(!st.isEmpty() && nums[k]>nums[st.peek()]){
                    res[st.peek()] = nums[k];
                    st.pop();
                }
                st.push(k);
            }

        }
        return res;


    }
}

LeetCode T42 接雨水

题目链接:42. 接雨水 - 力扣(LeetCode)

题目思路:

首先明确单调栈是这样计算雨水的,横向计算而不是竖向计算

下面我们考虑递减栈还是递增栈

明显是递增栈,我们需要找到前一个比他大的元素和后一个比他大的元素

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

如果遇到相同元素的怎么办??

此时选择弹出第一个相同元素或者不弹出其实都一样

弹出就是只计算一次,

不弹出的话第一次计算完中间高度就会变成5了

右边只要能找到一个大于5的,这样5就是最小值

然后计算高度的时候5减去中间柱子5就变成0了,也就等于没计算

只是计算方式不一样而已

使用宽*高来计算,最后相加就行

.

.

.

.

题目代码:

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

    }
}

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

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

相关文章

记录一次较为完整的Jenkins发布流程

文章目录 1. Jenkins安装1.1 Jenkins Docker安装1.2 Jenkins apt-get install安装 2. 关联github/gitee服务与webhook2.1 配置ssh2.2 Jenkins关联2.3 WebHook 3. 前后端关联发布 1. Jenkins安装 1.1 Jenkins Docker安装 Docker很好&#xff0c;但是我没有玩明白如何使用Docke…

【并发编程】Synchronized原理详解

&#x1f4eb;作者简介&#xff1a;小明java问道之路&#xff0c;2022年度博客之星全国TOP3&#xff0c;专注于后端、中间件、计算机底层、架构设计演进与稳定性建设优化&#xff0c;文章内容兼具广度、深度、大厂技术方案&#xff0c;对待技术喜欢推理加验证&#xff0c;就职于…

广州华锐互动VRAR | VR课件内容编辑器解决院校实践教学难题

VR课件内容编辑器由VR制作公司广州华锐互动开发&#xff0c;是一款专为虚拟现实教育领域设计的应用&#xff0c;它能够将传统的教学内容转化为沉浸式的三维体验。通过这款软件&#xff0c;教师可以轻松创建和编辑各种虚拟场景、模型和动画&#xff0c;以更生动、直观的方式展示…

.NET6使用MiniExcel根据数据源横向导出头部标题及数据

.NET6MiniExcel根据数据源横向导出头部标题 MiniExcel简单、高效避免OOM的.NET处理Excel查、写、填充数据工具。 特点: 低内存耗用&#xff0c;避免OOM、频繁 Full GC 情况 支持即时操作每行数据 兼具搭配 LINQ 延迟查询特性&#xff0c;能办到低消耗、快速分页等复杂查询 轻量…

CommonModule.dll动态链接库(DLL)文件丢失的处理方法

方法一、手动下载修复 (1)从网站下载commonmodule.dll文件到您的电脑上。 (2)将commonmodule.dll文件复制到" X:\Windows\system32 " (X代表您系统所在目录盘符&#xff0c;如&#xff1a;C:\Windows\system32)目录下。 (3)在开始菜单中找到"运行(R)" 或…

数据结构--字符串的模式匹配

案例导入概念 朴素&#xff08;暴力&#xff09;模式匹配算法 定位操作&#xff1a; 计算时间复杂度 总结

解决 Python requests 库中 SSL 错误转换为 Timeouts 问题

解决 Python requests 库中 SSL 错误转换为 Timeouts 问题&#xff1a;理解和处理 SSL 错误的关键 在使用Python的requests库进行HTTPS请求时&#xff0c;可能会遇到SSL错误&#xff0c;这些错误包括但不限于证书不匹配、SSL层出现问题等。如果在requests库中设置verifyFalse&…

ES6有何新特性?(下篇)

目录 函数参数的默认值设置 rest参数 扩展运算符 Symbol 迭代器 生成器 Promise Class 数值扩展 对象方法扩展 模块化 大家好呀&#xff01;今天这篇文章继续为大家介绍ES6的新特性&#xff0c;上上上篇文章介绍了一部分&#xff0c;这篇文章会将剩下的部分新增的特…

ElasticSearch在Windows上的下载与安装

Elasticsearch是一个开源的分布式搜索和分析引擎&#xff0c;它可以帮助我们快速地搜索、分析和处理大量数据。Elasticsearch能够快速地处理结构化和非结构化数据&#xff0c;支持全文检索、地理位置搜索、自动补全、聚合分析等功能&#xff0c;能够承载各种类型的应用&#xf…

用平板当电脑副屏(spacedesk)双端分享

文章目录 1.准备工作2.操作流程1. 打开spacedesk点击2. 勾选USB Cable Android3. 用数据线连接移动端和pc端&#xff0c;选择仅充电4. 打开安装好的spacedesk 记得在win系统中设置扩展显示器&#xff1a; 1.准备工作 下载软件spacedesk Driver Console pc端&#xff1a; 移动…

uniapp小程序定位;解决调试可以,发布不行的问题

遇见这个问题&#xff1b;一般情况就两种 1、域名配置问题&#xff1b; 2、隐私协议问题 当然&#xff0c;如果你的微信小程序定位接口没开启&#xff1b;定位也会有问题&#xff1b; 第一种&#xff0c;小程序一般是腾讯地图&#xff1b;所以一般都会用https://apis.map.qq.co…

Android studio run 手机或者模拟器安装失败,但是生成了debug.apk

错误信息如下&#xff1a;Error Installation did not succeed. The application could not be installed&#xff1a;List of apks 出现中文乱码&#xff1b; 我首先尝试了打包&#xff0c;能正常安装&#xff0c;再次尝试了debug的安装包&#xff0c;也正常安装&#xff1…

LangChain 5易速鲜花内部问答系统

展示了一个完整的问答系统的实现&#xff0c;使用了Flask来构建Web界面、langchain进行文档处理和检索&#xff0c;以及OpenAI的语言模型。代码的复杂性在于集成了多种高级技术和处理大型数据集和语言模型。 LangChain 实现给动物取名字&#xff0c;LangChain 2模块化prompt t…

AVL树你需要了解一下

AVL树介绍 AVL树是一种自平衡二叉查找树&#xff0c;它得名于发明者G.M.Adel’son-Vel’skii和E.M.Landis。AVL树的特点是任何节点的两个子树的高度最大差别为1&#xff0c;因此它也被称为高度平衡树。在AVL树中&#xff0c;每个节点的平衡因子只有-1、0、1三种&#xff0c;通…

vue3 setup展示数据

效果图 1.创建数据 content.js import { reactive } from vueconst data reactive({color:red,title: 二十四节气,subTitle: 节气&#xff0c;是干支历中表示自然节律变化以及确立“十二月建”&#xff08;月令&#xff09;的特定节令。,list: [{name: "立春",con…

hdfsClient_java对hdfs进行上传、下载、删除、移动、打印文件信息尚硅谷大海哥

Java可以通过Hadoop提供的HDFS Java API来控制HDFS。通过HDFS Java API&#xff0c;可以实现对HDFS的文件操作&#xff0c;包括文件的创建、读取、写入、删除等操作。 具体来说&#xff0c;Java可以通过HDFS Java API来创建一个HDFS文件系统对象&#xff0c;然后使用该对象来进…

基于单片机GPS轨迹定位和里程统计系统

**单片机设计介绍&#xff0c; 基于单片机GPS轨迹定位和里程统计系统 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 一个基于单片机、GPS和里程计的轨迹定位和里程统计系统可以被设计成能够在移动的交通工具中精确定位车辆的位置…

clickhouse分布式之弹性扩缩容的故事

现状 社区不支持喔&#xff0c;以后也不会有了。曾经尝试过&#xff0c;难道是是太难了&#xff0c;无法实现吗&#xff1f;因为他们企业版支持了&#xff0c;可能是利益相关吧&#xff0c;谁知道呢&#xff0c;毕竟开源也要赚钱&#xff0c;谁乐意一直付出没有回报呢。 社区…

N 字形变换

将一个给定字符串 s 根据给定的行数 numRows &#xff0c;以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 “PAYPALISHIRING” 行数为 3 时&#xff0c;排列如下&#xff1a; P A H N A P L S I I G Y I R 之后&#xff0c;你的输出需要从左往右逐行读取&#xff0…

使用树莓派学习Linux系统编程的 --- 库编程(面试重点)

在之前的Linux系统编程中&#xff0c;学习了文件的打开&#xff1b;关闭&#xff1b;读写&#xff1b;进程&#xff1b;线程等概念.... 本节补充“Linux库概念 & 相关编程”&#xff0c;这是一个面试的重点&#xff01; 分文件编程 在之前的学习中&#xff0c;面对较大的…