当前位置: 首页 > news >正文

单调栈② | Java | LeetCode 接雨水 最大的矩形

42. 接雨水

暴力法

for循环遍历每一个柱子,内层for循环找到左边和右边比它高的柱子
时间复杂度 n^2

优化:添加一个预处理
定义一个数组,存放该柱子右边比他高的柱子是哪一个
再用一个数组,存放该柱子左边比他高的柱子是哪一个

单调栈

单调栈:在每日温度题目中,其要找到右边第一个比他大的温度;适配到本题,就是找到当前柱子左边&右边 第一个比它大的温度

遍历一次就能处理完:当前遍历的元素比栈口元素大的时候,说明栈口柱子右边比它大的那个柱子找到了,它左边比它大的柱子怎么找?在栈中。
在这里插入图片描述

class Solution {public int trap(int[] height){int size = height.length;if (size <= 2) return 0;// in the stack, we push the index of array// using height[] to access the real heightStack<Integer> stack = new Stack<Integer>();stack.push(0);int sum = 0;for (int index = 1; index < size; index++){int stackTop = stack.peek();if (height[index] < height[stackTop]){stack.push(index);}else if (height[index] == height[stackTop]){// 因为相等的相邻墙,左边一个是不可能存放雨水的,所以pop左边的index, push当前的indexstack.pop();stack.push(index);}else{//pop up all lower valueint heightAtIdx = height[index];while (!stack.isEmpty() && (heightAtIdx > height[stackTop])){int mid = stack.pop();if (!stack.isEmpty()){int left = stack.peek();int h = Math.min(height[left], height[index]) - height[mid];int w = index - left - 1;int hold = h * w;if (hold > 0) sum += hold; //加不加大于0都一样stackTop = stack.peek();}}stack.push(index);}}return sum;}
}
  • 自己再做了一遍
class Solution {public int trap(int[] height) {if(height.length <= 2) {return 0;}Stack<Integer> st = new Stack<>(); //存的是下标st.push(0);int sum = 0;for(int i=1; i<height.length; i++) {// i 下标  height[i]值// height[st.peek()]  height[st.pop()]if(height[i] < height[st.peek()]) {st.push(i);} else if(height[i] == height[st.peek()]) {st.pop();st.push(i); //虽然值是一样的,但下标不一样} else { //发现凹槽了// int stackTop = st.peek();int right = i; //凹槽右侧高度while(!st.empty() && height[right] > height[st.peek()]) {int mid = st.pop();//凹点if(!st.empty()) {int left = st.peek();int w = right-left-1;int h = Math.min(height[left], height[right]) - height[mid];int hold = h*w;sum += hold;}}st.push(i);//体积 = w * h }}return sum;}
}

双指针

与单调栈不同的是,双指针求体积求的是 竖向的体积

class Solution {public int trap(int[] height) {int len = height.length;if(len <= 2) return 0;int[]maxLeft = new int[len];int[]maxRight = new int[len];maxLeft[0] = height[0];for(int i=1; i<len; i++) {maxLeft[i] = Math.max(height[i], maxLeft[i-1]);}maxRight[len-1] = height[len-1];for(int i=len-2; i>=0; i--) {// maxLeft[i] = Math.max(height[i], maxLeft[i-1]);maxRight[i] = Math.max(height[i],maxRight[i+1]);}int sum = 0;for(int i=0; i<len; i++) {int h = Math.min(maxLeft[i],maxRight[i]) - height[i];if(h>0) sum+=h; // h*1}return sum;}
}

84.柱状图中最大的矩形

emmm 和接雨水到底哪里一样了???

暴力法 双指针

遍历每一根柱子,向左向右找比它小的边界,算出面积并求最大
优化:两个数组,一个存放i左边比他矮的,一个存放i右边

单调栈

写法不一样了,栈中元素 从栈顶到栈底要 从大到小。

遍历一次就能处理完:当前遍历的元素比栈口元素小的时候,说明栈口柱子右边比它小的那个柱子找到了,它左边比它小的柱子怎么找?在栈中。

  • 首尾补0
    尾补0:[2,4,6,8]
    首补0:[8,6,4,2]
class Solution {public int largestRectangleArea(int[] heights) {int[]newHeight = new int[heights.length+2];for(int i=1; i<=heights.length; i++) {newHeight[i] = heights[i-1];}heights = newHeight; //重定向Stack<Integer> st = new Stack<Integer>();st.push(0);int res=0;for(int i=1; i<heights.length; i++) {if(heights[i]>heights[st.peek()]) {st.push(i);} else if(heights[i] == heights[st.peek()]) {st.pop();st.push(i);} else {//栈可能为空吗?while(heights[i] < heights[st.peek()]) {int mid = st.peek();st.pop();int left = st.peek();int right = i;int w = right - left - 1;int h = heights[mid];res = Math.max(res, w * h);}st.push(i);}}return res;}
}

单调栈最核心的其实是栈顶元素

相关文章:

单调栈② | Java | LeetCode 接雨水 最大的矩形

42. 接雨水 暴力法 for循环遍历每一个柱子&#xff0c;内层for循环找到左边和右边比它高的柱子 时间复杂度 n^2 优化&#xff1a;添加一个预处理 定义一个数组&#xff0c;存放该柱子右边比他高的柱子是哪一个 再用一个数组&#xff0c;存放该柱子左边比他高的柱子是哪一个 …...

2024年全国青少年信息素养大赛总决赛日赛程表

2024全国青少年信息素养大赛赛程表分赛场&#xff08;浙江传媒学院桐乡校区、桐乡技师学院&#xff09;日期地点时间赛项16日传媒学院8:00-9:00检录 9:00-10:30开赛图形化编程挑战赛&#xff08;小学1-3年级&#xff09;A组12:00-13:00检录 13:00-14:30开赛图形化编程挑战赛&am…...

PHP:连接钉钉接口-钉钉回调事件,本地测试数据

前置数据参考 数据说明&#xff1a;参见官方文档回调事件消息体加解密 - 钉钉开放平台 (dingtalk.com) URL后面带的参数&#xff1a; signature5a65ceeef9aab2d149439f82dc191dd6c5cbe2c0&timestamp1445827045067&noncenEXhMP4r Post参数&#xff1a; { &quo…...

【C++标准模版库】vector的介绍及使用

vector 一.vector的介绍二.vector的使用1.vector 构造函数2.vector 空间增长3.vector 增删查改4.vector 迭代器的使用1.正向迭代器2.反向迭代器 5.victor 迭代器失效问题&#xff08;重点&#xff09; 三.vector不支持 流提取与流插入四.vector存储自定义类型1.存储string2.存储…...

数说故事|引爆社媒的森贝儿IP,品牌如何实现流量变现?

以可爱、雅痞、贱萌......的外表加魔性舞姿出圈的可爱小狗——森贝儿贵宾犬Milo&#xff0c;用“可爱微怒”的表情演绎着当代打工人的“疯态”&#xff0c;并迅速晋升成不少打工人高频使用的表情包。 最近几年&#xff0c;“萌系”爆款IP频出&#xff0c;用小动物的形象、可爱…...

使用openpyxl库对Excel条件格式的深度探索

哈喽,大家好,我是木头左! openpyxl中的条件格式 在openpyxl中,可以使用ConditionalFormatting类来创建和管理条件格式。这个类有两个主要的方法:add_conditional_formatting()和remove_conditional_formatting(),分别用于添加和删除条件格式。 add_conditional_formatt…...

原生javascript中的ajax通信技术

AJAX&#xff08;Asynchronous JavaScript and XML&#xff09;是一种在无需重新加载整个网页的情况下&#xff0c;能够更新部分网页的技术。也就是实现前后端交互的功能。以下是使用AJAX的基本步骤和代码演示&#xff1a; 1.创建一个XMLHttpRequest对象&#xff1a; var xhr…...

SpringBoot Vue用自签名证书SSL配置https,http转发到https(整理文章)

要配置https地址访问&#xff0c;需要向服务器商申请和使用SSL证书。由于是测试阶段&#xff0c;我们自己创建SSL证书&#xff0c;叫作自签名证书。 1.创建自签名证书 Vue前端生成自签名证书我们用openssl 参考文章一 参考文章二SpringBoot后端生成自签名证书用JDK自带的keyt…...

嵌入式人工智能(41-基于树莓派4B的串口蓝牙模块AT09-cc2541)

1、串口蓝牙模块AT-09 AT-09是一种串口蓝牙模块&#xff0c;可实现串口与蓝牙之间的数据传输。AT-09模块基于蓝牙4.0技术&#xff0c;具有低功耗、高传输速率和广泛的应用范围。 AT-09模块支持AT指令&#xff0c;通过串口与外部设备进行通信。用户可以使用AT指令对模块进行配…...

C++ 动态规划

子序列子串相关 单个指一个数组或字符串&#xff0c;两个指两个数组或字符串。 最长上升子序列-单个 dp[i]&#xff1a;以下标i为结尾的递增的最长子序列长度。 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 1 的最大值。 class Solution { public:int l…...

回溯问题总结

一、子集问题 模板问题 给定一个序列[1,n],求这个序列的所有子集 输入描述&#xff1a; 一个正整数n(1 < n < 12) 输出描述&#xff1a; 每个子集一行&#xff0c;输出所有子集。 输出顺序为&#xff1a; &#xff08;1&#xff09;元素个数少的子集优先输出&#xff1b;…...

GraphRAG如何使用ollama提供的llm model 和Embedding model服务构建本地知识库

使用GraphRAG踩坑无数 在GraphRAG的使用过程中将需要踩的坑都踩了一遍&#xff08;不得不吐槽下&#xff0c;官方代码有很多遗留问题&#xff0c;他们自己也承认工作重心在算法的优化而不是各种模型和框架的兼容性适配性上&#xff09;&#xff0c;经过了大量的查阅各种资料以…...

.net # 检查 带有pdf xss

1.解决pdf含javasprct脚本动作&#xff0c;这里是验证pdf内部事件。相关pdf文件下载&#xff1a; 测试pdf文件 相关包 iTextSharp 5.5.13.4 iTextSharp using iTextSharp.text.pdf; using iTextSharp.text.pdf.parser;private Boolean IsPdfSafe(Stream stream){// PdfReader…...

【React】探讨className的正确使用方式

文章目录 一、className的正确用法二、常见错误解析三、实例解析四、错误分析与解决五、注意事项六、总结 在React开发中&#xff0c;正确使用className属性对组件进行样式设置至关重要。然而&#xff0c;由于JavaScript和JSX的特殊性&#xff0c;开发者常常会犯一些小错误&…...

打靶记录5——靶机hard_socnet2

靶机&#xff1a; https://download.vulnhub.com/boredhackerblog/hard_socnet2.ova目标&#xff1a; 取得root权限 涉及攻击方法 主机发现端口扫描SQL注入文件上传蚁剑上线XMLRPC命令执行逆向工程动态调试漏洞利用代码编写 方法 CVE-2021-3493缓冲器溢出漏洞 学习目标 …...

独立站+TikTok达人:自主营销与创意内容的完美结合

在全球电商市场迅猛发展的今天&#xff0c;独立站和TikTok达人的结合正在创造一种全新的电商营销模式。独立站作为电商平台&#xff0c;其自主性和灵活性为商家提供了广阔的发展空间&#xff1b;而TikTok达人凭借其独特的内容创作能力和庞大的粉丝基础&#xff0c;成为推动销售…...

【启明智显分享】适用于多功能养生壶、茶吧机的2.8寸触摸彩屏解决方案

健康生活理念不断深入人心&#xff0c;多功能养生壶、茶吧机等智能产品成为现代家庭的热门小家电。为推动智能家居个性化、多样化发展&#xff0c;启明智显推出了基于SC05 Plus 2.8寸触摸彩屏的多功能养生壶、茶吧机的解决方案&#xff0c;旨在提升养生壶与茶吧机的用户体验与操…...

WAF绕过技术(PKAV团队)

目录 主流WAF的绕过技术 Web容器的特性 1. IIS+ASP的神奇% 2. IIS的Unicode编码字符 3. HPP(HTTP Parameter Pollution): HTTP参数污染 4. 畸形HTTP请求 Web应用层的问题 1. 多重编码问题 2. 多数据来源的问题 WAF自身的问题 1. 白名单机制 2. 数据获取方式存在缺陷…...

『 Linux 』POSIX 信号量与基于环形队列的生产者消费者模型

文章目录 信号量概念POSIX 信号量基于环形队列的生产者消费者模型基于环形队列的生产者消费者模型编码实现基于环形队列的生产者消费者模型发送任务测试 信号量概念 信号量是一种用于多线程或多进程间同步的机制; 其定义是一个整形变量,本质上信号量可以看成是一个计数器,用来描…...

python中的字符串方法

python中的字符串 举个例子先 name = 貂蝉开大 #声明了一个字符串 print(name) # 打印了一个字符串 print(name[0:1] #输出貂蝉 print(name[2:3] #输出开大 扩展方法 find() # 查找字符串中某个字符的索引 index_ = name.find("貂") print(index_) # 输出 …...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...