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

单调栈问题

原理

单调栈的核心原理是:在栈内保持元素的单调性(递增或递减)

单调递增栈

用于处理“下一个更小的元素”问题。当新元素比栈顶元素小或等于时,直接入栈;否则,一直从栈顶弹出元素,直到栈顶元素小于新元素或栈为空。

单调递减栈:

用于处理“下一个更大的元素”问题。当新元素比栈顶元素大时,一直从栈顶弹出元素,直到栈顶元素大于新元素或栈为空,然后将新元素入栈。

核心代码框架

#include <vector>
#include <stack>
using namespace std;vector<int> nextGreaterElement(vector<int>& nums) {int n = nums.size();vector<int> res(n, -1);  // 默认值为-1,表示没有找到stack<int> stk;          // 用于存储元素索引的单调栈for (int i = 0; i < n; i++) {// 维护栈的单调递减性while (!stk.empty() && nums[stk.top()] < nums[i]) {int idx = stk.top(); // 栈顶元素索引stk.pop();res[idx] = nums[i]; // 找到了下一个更大的元素}stk.push(i); // 入栈当前元素索引}return res;
}

739. 每日温度

在这里插入图片描述

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> res(n,0);stack<int>stk;for(int i = 0;i<n;i++){// 递增while(!stk.empty() && temperatures[stk.top()]<temperatures[i]){int index = stk.top(); // 栈顶元素stk.pop();res[index] = i-index;//res[index] = temperatures[i];}stk.push(i);}for(int i = 0;i<n;i++){cout<<res[i]<<endl;}return res;}
};

496.下一个更大元素 I

在这里插入图片描述
思路:暴力法

直接足步循环
先找到和 nums1 对应的 nums2 数,找到后,在循环找更大的,找到就退出

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();int m = nums2.size();vector<int> res (n,-1); // -1代表没找到stack<int>stk;for(int i = 0;i<n;i++){int j = 0;while(nums1[i] != nums2[j]){j++;}for(int k = j+1; k<m;k++){if(nums2[k]>nums1[i]){res[i] = nums2[k];break;}}}return res;}
};

思路二:单调栈

我们可以先对 nums2 进行单调栈,找到他每个元素的的下一个更大的数
再根据 nums1 创建数组

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();int m = nums2.size();unordered_map<int, int> nxetnum;vector<int> res (n,-1); // -1代表没找到stack<int>stk;// 遍历 nums2for(int num : nums2){while(!stk.empty()&& stk.top()<num){nxetnum[stk.top()] = num;stk.pop();}stk.push(num);}// 如果没有更大元素,则对应结果为 -1;while(!stk.empty()){nxetnum[stk.top()] = -1;stk.pop();}// 从nums1 中查找对应的;for(int i = 0;i<n;i++){res[i] = nxetnum[nums1[i]];}return res;}
};

503.下一个更大元素II

在这里插入图片描述
思路:

因为可以循环,直接将数组进行拼接,这样就破解循环问题了,就如同前面的每日温度问题了

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {int n = nums.size();vector<int>realnums;// 暴力拼接for(int i = 0; i<2;i++){for(int num:nums){realnums.push_back(num);}}vector<int> res(2*n,-1);stack<int>stk;for(int i = 0;i<realnums.size();i++){while(!stk.empty() && realnums[stk.top()]<realnums[i]){int index = stk.top();stk.pop();res[index] = realnums[i];}stk.push(i);}vector<int>resnum;resnum.insert(resnum.end(),res.begin(),res.begin()+n);return resnum;}
};

代码优化一下:

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {int n = nums.size();vector<int>realnums(n,-1);stack<int>stk;for(int i = 0 ;i<2*n;i++){int num = nums[i % n];while(!stk.empty() && nums[stk.top()] <num){int index = stk.top();stk.pop();realnums[index]  = num;}if(i<n){stk.push(i);}}return realnums;}
};

相关文章:

单调栈问题

原理 单调栈的核心原理是&#xff1a;在栈内保持元素的单调性&#xff08;递增或递减&#xff09; 单调递增栈&#xff1a; 用于处理“下一个更小的元素”问题。当新元素比栈顶元素小或等于时&#xff0c;直接入栈&#xff1b;否则&#xff0c;一直从栈顶弹出元素&#xff0c…...

Hexo博客重新部署与Git配置

由于电脑重装了一次&#xff0c;发现之前Hexo与NexT主题版本过于落后&#xff0c;重新部署了下。 1 Node.js与git安装 这一块安装就不赘述了。去两个官网找安装文件安装即可。 node.js git 打开git以后配置的几个关键命令行。 git config --global user.name "你的gi…...

KUKA机器人专业名词解释

1、CCU Cabinet Control Unit &#xff08;控制柜控制单元&#xff09; 2、CIB Cabinet Interface Board &#xff08;控制柜接口板&#xff09; 3、HMI Human Machine Interface &#xff08;人机界面&#xff09;&#xff1b;KUKA.HMI 是 KUKA 操作界面。 4、KCB …...

阿里云 物联网平台 MQTT连接、数据传输

阿里云 物联网平台 MQTT连接、数据传输 1、设备连接阿里云 2、多设备之前的通信、数据流转 3、设备数据来源的读取。 基于C# winform 开发上位机&#xff0c;读取设备、仪器、MES或者电子元器件的数据&#xff0c;MQTT传输至阿里云平台&#xff0c;可视化界面构建界面&#…...

栈和队列OJ练习题及解答

前言 上一篇博客已经讲到了栈和队列的数据结构&#xff0c;概括一下&#xff1a;栈后进先出&#xff08;Last In First Out&#xff09;、队列先进先出&#xff08;First In First Out&#xff09;。那么&#xff0c;接下来就来讲讲&#xff0c;关于栈和队列的相关练习题&#…...

渗透测试-信息收集

网络安全信息收集是网络安全领域中至关重要的一环&#xff0c;它涉及到对目标系统、网络或应用进行全面而细致的信息搜集和分析。这一过程不仅有助于理解目标网络的结构、配置和潜在的安全风险&#xff0c;还能为后续的渗透测试、风险评估和安全加固提供有力的支持。 在网络安…...

电力乙级资质延伸换证:企业转型的契机

电力乙级资质延伸换证不仅是企业合规运营的必要步骤&#xff0c;同时也为企业转型提供了重要的契机。在这个过程中&#xff0c;企业可以重新审视自身的业务模式、管理体系、技术能力等方面&#xff0c;寻找新的增长点和发展方向。 首先&#xff0c;电力乙级资质延伸换证要求企业…...

基于Redis实现分布式锁——Java版本

基于Redis实现分布式锁——Java版本 版本一版本二版本三Redisson 定义分布式锁接口如下&#xff1a; public interface ILock {boolean tryLock(long timeoutSec);void unlock(); }版本一 设定业务超时时间&#xff0c;到期自动解锁。缺点是超时时间不好估计&#xff0c;需要…...

Qt自定义控件--提升为

为什么要自定义控件 1&#xff0c;有复合小控件需要组合为一个整体控件时&#xff1b; 2&#xff0c;一个复合控件需要重复使用时&#xff1b; 实现 自定义控件文件 新增三个文件 关联不同组的控件 关联之前的准备工作 1&#xff0c;在主控件选择和子控件所有控件所在控件…...

Lua 基础 01 入门

Lua 基础相关知识 第一期 注释 -- 单行注释--[[多行注释 --]]-- 多加一个横杠符号就能重新启用注释内的代码 ---[[print("Lua") --]]数据类型 Lua 是动态类型语言&#xff0c;变量不需要类型定义&#xff0c;只需要为变量赋值。 Lua 有 8 种基本类型&#xff1a…...

远程连接阿里云ECS

说明&#xff1a;ECS&#xff08;阿里云服务器&#xff09;可选择的系统镜像如下&#xff1a; 本文介绍基于Windows系统&#xff0c;对CentOS、Ubuntu、Windows这三个操作系统的连接方式&#xff0c;以及连接工具Windterm的使用。 CentOS & Windterm CentOS是我使用时间最…...

【C++】多态(上)超详细

封装&#xff0c;继承&#xff0c;多态不只是C的三大特性&#xff0c;而是面向对象编程的三大特性。 什么是多态&#xff1a; 不同的对象做同一件事情&#xff0c;结果会出现多种形态。 1.满足多态的几个条件 1.父子类完成虚函数重写&#xff08;需要满足三同&#xff1a;函…...

【Git】 Git分支操作指南

隐形的纪念躲在心里面 也许吧 也许不会再见 阴天或晴天 一天又一年 风它在对我说莫忘这一切 &#x1f3b5; 蔡淳佳《隐形纪念》 Git是一种非常强大的分布式版本控制系统&#xff0c;允许用户在开发过程中创建不同的分支&#xff08;branch&#xff09;来分…...

智慧文旅赋能旅游服务升级:以科技创新驱动行业变革,打造智慧化、个性化、高效化的旅游新体验,满足游客日益增长的多元化需求

目录 一、引言 二、智慧文旅的概念与内涵 三、智慧文旅在旅游服务升级中的应用 1、智慧旅游服务平台建设 2、智慧景区管理 3、智慧旅游营销 四、智慧文旅推动旅游行业变革的案例分析 案例一&#xff1a;某智慧旅游城市建设项目 案例二&#xff1a;某景区智慧化改造项目…...

AtCoder Beginner Contest 310 E题 NAND repeatedly

E题&#xff1a;NAND repeatedly 标签&#xff1a;动态规划题意&#xff1a;给定一个长度为 n n n的 01 01 01字符串 A i A_i Ai​&#xff0c;给定规则&#xff1a; 0 ⊼ 0 1 , 0 ⊼ 1 1 , 1 ⊼ 0 1 , 1 ⊼ 1 0 0⊼01,0⊼11,1⊼01,1⊼10 0⊼01,0⊼11,1⊼01,1⊼10。 求 ∑…...

一款简易的免费抽奖软件

一、介绍 这款抽奖软件设计简洁&#xff0c;操作便捷。用户可以轻松将参与名单通过EXCEL文件导入至程序中&#xff0c;并可根据需要设定各类奖品和对应的中奖人数。在选定了奖品后&#xff0c;用户只需点击“开始”按钮&#xff0c;随后再按下“暂停”按钮&#xff0c;软件便会…...

Kubernetes 监控管理

目录 1. Metrics Server2. Prometheus & Grafana3. cAdvisor4. 日志收集5. 告警与通知6. 最佳实践 Kubernetes 监控管理是确保集群稳定运行和应用服务质量的关键环节。它涉及收集、聚合、分析集群及其上运行的应用程序的各种指标和日志数据。 1. Metrics Server 作用&…...

哈希表第6/9题--四数相加II

题目描述&#xff1a; 给你四个整数数组 nums1、nums2、nums3 和 nums4 &#xff0c;数组长度都是 n &#xff0c;请你计算有多少个元组 (i, j, k, l) 能满足&#xff1a; 0 < i, j, k, l < nnums1[i] nums2[j] nums3[k] nums4[l] 0 示例 1&#xff1a; 输入&…...

使用JavaScript将富文本HTML转换为纯文本

在Web开发中&#xff0c;我们经常需要处理HTML内容&#xff0c;但有时为了特定的目的&#xff0c;比如文本处理、搜索或显示在非HTML环境中&#xff0c;我们可能希望将富文本HTML转换为纯文本。这里&#xff0c;我们将探讨如何使用JavaScript来实现这一功能。 为什么要将HTML转…...

2024-05-13 问AI: 介绍一下 google wavenet 声码器

文心一言 Google的WaveNet声码器是一个深度学习模型&#xff0c;用于生成高质量的音频信号&#xff0c;特别是人类语音。与传统的声码器相比&#xff0c;WaveNet可以生成更加自然和流畅的音频&#xff0c;因为它直接模拟了原始音频信号的波形生成过程。 WaveNet的核心思想是使…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...