当前位置: 首页 > 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的核心思想是使…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

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

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...

Xcode 16 集成 cocoapods 报错

基于 Xcode 16 新建工程项目&#xff0c;集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...

EasyRTC音视频实时通话功能在WebRTC与智能硬件整合中的应用与优势

一、WebRTC与智能硬件整合趋势​ 随着物联网和实时通信需求的爆发式增长&#xff0c;WebRTC作为开源实时通信技术&#xff0c;为浏览器与移动应用提供免插件的音视频通信能力&#xff0c;在智能硬件领域的融合应用已成必然趋势。智能硬件不再局限于单一功能&#xff0c;对实时…...