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

【算法日志】单调栈: 单调栈简介及其应用

代码随想录刷题60Day


目录

单调栈简介

单调栈的应用

下次更高温

下一个更大元素1

下一个更大元素2

接雨水

柱状图中最大矩形


单调栈简介

单调栈(Monotonic Stack)是一种特殊的栈数据结构,它满足元素的单调性,这种单调性需要自己建立和维护。单调栈分为单调递增栈和单调递减栈两种类型。

单调递增栈的特点是栈内元素从栈底到栈顶依次递增,而单调递减栈则是栈内元素从栈底到栈顶依次递减。

单调栈的主要应用是解决一些与找到元素的下一个更大或更小相关的问题。它通过维护一个递增或递减的栈,可以在常数时间内找到每个元素的下一个更大或更小的元素。

单调栈的基本操作包括:

入栈:将元素压入栈顶,同时保持栈的单调性。

出栈:从栈顶移除元素。

查找:检查栈顶元素,获取当前元素的下一个更大或更小的元素。

单调栈的应用

下次更高温

    vector<int> dailyTemperatures(vector<int>& temperatures) {int size = temperatures.size();vector<int> result(size, 0);stack<int> stack;stack.push(0);for (int i = 1; i < size; ++i){int j = stack.top();if (temperatures[i] > temperatures[j]){while (!stack.empty() && temperatures[i] > temperatures[j]){result[j] = i - j;stack.pop();if (!stack.empty())j = stack.top();}}stack.push(i);}return result;}

下一个更大元素1

	vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {int size1 = nums1.size();int size2 = nums2.size();unordered_map<int, int> umap;stack<int> stack;vector<int> result;stack.push(0);for (int i = 1; i < size2; ++i){int j = stack.top();if (nums2[j] < nums2[i]){while (!stack.empty() && nums2[j] < nums2[i]){umap.insert(pair<int, int>(nums2[j], nums2[i]));stack.pop();if (!stack.empty())j = stack.top();}}stack.push(i);}for (int i = 0; i < size1; ++i){if (umap.find(nums1[i]) != umap.end())result.push_back(umap[nums1[i]]);elseresult.push_back(-1);}return result;}

下一个更大元素2

	vector<int> nextGreaterElements(vector<int>& nums) {int size = nums.size();vector<int> dp(size, -1);stack<int> mystack;mystack.push(0);for (int i = 1; i < size; ++i){if (nums[i] > nums[mystack.top()]){while (!mystack.empty() && nums[i] > nums[mystack.top()]){dp[mystack.top()] = nums[i];if (!mystack.empty())mystack.pop();					}}mystack.push(i);}for (int i = 0; i < size; ++i){if (nums[i] > nums[mystack.top()]){while (!mystack.empty() && nums[i] > nums[mystack.top()]){dp[mystack.top()] = nums[i];if (!mystack.empty())mystack.pop();					}}mystack.push(i);}return dp;}

接雨水

	int trap(vector<int>& h){if (h.size() < 3)return 0;stack<int> mystack;int result = 0;mystack.push(0);for (int i = 1; i < h.size(); ++i){if (h[mystack.top()] > h[i])mystack.push(i);else if (h[mystack.top()] < h[i]){while (!mystack.empty() && h[mystack.top()] < h[i]){int mid = mystack.top();mystack.pop();if (!mystack.empty())result += (min(h[mystack.top()], h[i]) - h[mid]) * (i - mystack.top() - 1);				}if (!mystack.empty() && h[mystack.top()] == h[i])mystack.pop();mystack.push(i);}else{mystack.pop();mystack.push(i);}}return result;}

柱状图中最大矩形

	int largestRectangleArea(vector<int>& h) {h.push_back(0);int size = h.size();stack<int> mystack;int result = h[0];mystack.push(0);for (int i = 1; i < size; ++i){if (h[i] == h[mystack.top()]){mystack.pop();}else if (h[i] < h[mystack.top()]){int mid, left;while (!mystack.empty() && h[i] < h[mystack.top()]){mid = mystack.top();mystack.pop();if (!mystack.empty())left = mystack.top();elseleft = -1;result = max(result, (i - left - 1) * h[mid]);}}mystack.push(i);}return result;}

相关文章:

【算法日志】单调栈: 单调栈简介及其应用

代码随想录刷题60Day 目录 单调栈简介 单调栈的应用 下次更高温 下一个更大元素1 下一个更大元素2 接雨水 柱状图中最大矩形 单调栈简介 单调栈&#xff08;Monotonic Stack&#xff09;是一种特殊的栈数据结构&#xff0c;它满足元素的单调性&#xff0c;这种单调性需…...

VSCode自动分析代码的插件

今天来给大伙介绍一款非常好用的插件&#xff0c;它能够自动分析代码&#xff0c;并帮你完成代码的编写 效果如下图 首先我们用的是VSCode&#xff0c;&#xff08;免费随便下&#xff09; 找到扩展&#xff0c;搜索CodeGeeX&#xff0c;将它下载好&#xff0c;就可以实现了 到…...

设计模式之外观模式

文章目录 影院管理项目传统方式解决影院管理传统方式解决影院管理问题分析外观模式基本介绍外观模式原理类图外观模式解决影院管理传统方式解决影院管理说明外观模式应用实例 外观模式的注意事项和细节 影院管理项目 组建一个家庭影院&#xff1a; DVD 播放器、投影仪、自动屏…...

Web端测试和 App端测试有何不同?

Web 端测试和 App 端测试是针对不同平台的上的应用进行测试&#xff0c;Web应用和App端的应用实现方式不同&#xff0c;测试时的侧重点也不一样。 今天这篇文章就来介绍下两者的不同之处以及测试时的侧重点。 同时&#xff0c;我也准备了一份软件测试面试视频教程&#xff08…...

12.(Python数模)(相关性分析一)相关系数矩阵

相关系数矩阵 相关系数矩阵是用于衡量多个变量之间关系强度和方向的统计工具。它是一个对称矩阵&#xff0c;其中每个元素表示对应变量之间的相关系数。 要计算相关系数矩阵&#xff0c;首先需要计算每对变量之间的相关系数。常用的相关系数包括皮尔逊相关系数和斯皮尔曼相关…...

系统架构设计师(第二版)学习笔记----嵌入式系统及软件

【原文链接】系统架构设计师&#xff08;第二版&#xff09;学习笔记----嵌入式系统及软件 文章目录 一、嵌入式系统1.1 嵌入式系统的组成1.2 嵌入式系统的特点1.3 嵌入式系统的分类 二、嵌入式软件2.1 嵌入式系统软件分层2.2 嵌入式软件的主要特点 三、安全攸关软件的安全性设…...

Python列表操作指南:索引、切片、遍历与综合应用

文章目录 列表简介创建列表索引和切片列表的长度列表的拼接和重复检查元素是否存在列表的方法index() 方法count() 方法 列表的修改和删除修改元素删除元素列表的排序和反转添加元素 列表的拷贝列表的遍历列表的切片列表的嵌套列表推导式 python精品专栏推荐python基础知识&…...

第15章_锁: MySQL并发访问相同记录以及从数据操作的类型划分锁(读锁、写锁)

事务的 隔离性 由这章讲述的 锁 来实现。 1. 概述 锁是计算机协调多个进程或线程并发访问某一资源的机制. 在程序开发中会存在多线程同步的问题, 当多个线程并发访问某个数据的时候, 尤其是针对一些敏感数据(订单, 金额), 我们就需要保证这个数据在任何时刻最多只有一个线…...

PHP 排序函数使用方法,按照字母排序等操作

详解PHP排序方法使用 一、sort() 函数 用于对数组单元从低到高进行排序。 //数组 $data array(D,F,A,C,B); //排序 sort($data); //输出排版标签 echo "<pre>"; //打印数据 print_r($data);die;输出结果&#xff1a; 二、rsort() 函数 用于对数组单元从高到…...

windows本地验证码识别工具

windows本地验证码识别小工具 - 可以用在windows系统中&#xff0c;并可以集成在Java或python程序中 演示视频如下&#xff1a;可用于识别4-7位的字母数字组合的验证码&#xff08;识别准确率在70% - 80%&#xff09;。 验证码识别演示 本项目未开源&#xff0c;如需使用请联…...

修改图片尺寸的几个简单方法

修改图片尺寸的几个简单方法~~图片&#xff0c;是我们常用的文件格式&#xff0c;也是日常生活与工作中重要的文件。图片记录了非常多的元素和内容&#xff0c;其中不乏有工作上的内容&#xff0c;也有对一些日常生活的记录。所以说&#xff0c;图片文件对我们来说是非常重要的…...

三、GoLang字符串的基本操作

一、转义符是什么? 转义字符意义\n换行&#xff0c;将当前位置移动到下一行开头\r回车&#xff0c;将当前位置移到本行开头\t相当于一个Tab键\\代表一个反斜线“\”\"代表一个双引号字符 代码实战 package mainimport "fmt"/* *字符串基本用法 */ func main…...

基于vue-cli创建后台管理系统前端页面——element-ui,axios,跨域配置,布局初步,导航栏

目录 引出安装npm install安装element-ui安装axios 进行配置main.js中引入添加jwt前端跨域配置 进行初始布局HomeView.vueApp.vue 新增页面和引入home页面导航栏总结 引出 1.vue-cli创建前端工程&#xff0c;安装element-ui&#xff0c;axios和配置&#xff1b; 2.前端跨域的配…...

在 ubuntu20.04 上安装 Pytorch

参考资料&#xff1a;https://www.linode.com/docs/guides/pytorch-installation-ubuntu-2004/ sudo apt update sudo apt install nvidia-cuda-toolkit (3G) mkdir anaconda cd ~/anaconda wget https://repo.anaconda.com/archive/Anaconda3-2020.11-Linux-x86_64.sh chmod …...

远程恋爱网站部署秘籍——群晖虚拟机助ni秀恩爱

文章目录 前言1. 安装网页运行环境1.1 安装php1.2 安装webstation 2. 下载网页源码文件2.1 访问网站地址并下载压缩包2.2 解压并上传至群辉NAS 3. 配置webstation3.1 配置网页服务3.2 配置网络门户 4. 局域网访问静态网页配置成功5. 使用cpolar发布静态网页&#xff0c;实现公网…...

vscode c++解决包含头文件红色波浪线问题

安装c/c插件后&#xff0c;按ctrlshiftp&#xff0c; 点击打开了c_cpp_properties.json文件&#xff0c;对其中的IncludePath进行编辑&#xff0c;示例如下&#xff1a; "includePath": ["${workspaceFolder}/**","${workspaceFolder}/include/**&q…...

PostgreSQL docker compose安装配置

docker-compose.yml如下&#xff1a; version: 3services:postgres:image: postgres:15.4healthcheck:test: [ "CMD", "pg_isready", "-q", "-d", "postgres", "-U", "root" ]timeout: 45sinterval: 1…...

电脑文件批量重命名:高效操作技巧

随着时间的推移&#xff0c;我们积累的文件和文件夹数量越来越多&#xff0c;需要对它们进行合理的命名和管理&#xff0c;以便更方便地查找和利用。而文件批量重命名功能可以帮助我们更高效地管理文件夹。下面介绍五种方式&#xff0c;帮助你更好地利用文件批量重命名工具&…...

c高级day4(shell)

实现一个对数组求和的函数&#xff0c;数组通过实参传递给函数写一个函数&#xff0c;输出当前用户的uid和gid&#xff0c;并使用变量接收结果...

整十粉丝庆祝文章系列内容征集建议

亲爱的读者们&#xff0c;大家好&#xff01; 作为一名文章作者&#xff0c;我深知没有读者的支持和喜爱&#xff0c;我的文字就只是无意义的文字堆积。因此&#xff0c;为了庆祝与感谢大家长久以来的支持&#xff0c;我准备举办一场特别的活动——粉丝庆祝文章系列内容征集建…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...