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

代码随想录第46期 单调栈

这道题主要是单调栈的简单应用

class Solution {
public:vector<int> dailyTemperatures(vector<int>& T) {vector<int> result(T.size(),0);stack<int> st;st.push(0);for(int i=1;i<T.size();i++){if(T[i]<=T[st.top()]){st.push(i);}else{while(!st.empty()&&T[i]>T[st.top()]){result[st.top()]=i-st.top();st.pop();}st.push(i);}}return result;}
};

暴力模拟

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> result;for(int i=0;i<nums1.size();i++){int j=0;while(nums1[i]!=nums2[j]){j++;}while(j<nums2.size()&&nums1[i]>=nums2[j]){j++;}if(j>=nums2.size()){result.push_back(-1);}else{int val=nums2[j];result.push_back(val);}}return result;}
};

单调栈

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> result(nums1.size(),-1);stack<int> st;st.push(0);unordered_map<int, int> umap; // key:下标元素,value:下标for (int i = 0; i < nums1.size(); i++) {umap[nums1[i]] = i;}for(int i=1;i<nums2.size();i++){if(nums2[i]<=nums2[st.top()]){st.push(i);}else{while(!st.empty()&&nums2[i]>nums2[st.top()]){if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标result[index] = nums2[i];}st.pop();}st.push(i);}}return result;}
};

比上一题多了个处理循环的操作

可以是模拟循环

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> result(nums.size(),-1);stack<int> st;st.push(0);for(int i=1;i<nums.size()*2;i++){if(nums[i%nums.size()]<=nums[st.top()]){st.push(i%nums.size());}else{while(!st.empty()&&nums[i%nums.size()]>nums[st.top()]){result[st.top()]=nums[i%nums.size()];st.pop();}st.push(i%nums.size());}}// 最后再把结果集即result数组resize到原数组大小result.resize(nums.size());return result;}
};

也可以是直接扩充数组

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> nums1(nums.begin(), nums.end());nums.insert(nums.end(), nums1.begin(), nums1.end());vector<int> result(nums.size(),-1);stack<int> st;st.push(0);unordered_map<int,int> umap;for(int i=0;i<nums.size();i++){if(nums[i]<=nums[st.top()]){st.push(i);}else{while(!st.empty()&&nums[i]>nums[st.top()]){result[st.top()]=nums[i];umap[st.top()]=nums[i];st.pop();}st.push(i);}}// 最后再把结果集即result数组resize到原数组大小result.resize(nums.size() / 2);return result;}
};

这道题同样是一个双指针问题

class Solution {
public:int trap(vector<int>& nums) {
// max(min{左max,右max}-arr[i],0)
//预处理最大值  left:0-0最大值  0-1最大 0-i最大值
//          right:12-12最大值,11-12最大值 i-12最大值
/*int n=height.size();
int *lmax=new int[n];
int *rmax=new int[n];
lmax[0]=height[0];
for(int i=1;i<n;i++){
lmax[i]=max(lmax[i-1],height[i]);
}
rmax[n-1]=height[n-1];
for(int i=n-2;i>=0;i--){
rmax[i]=max(rmax[i+1],height[i]);
}
int ans=0;
for(int i=1;i<n-1;i++){ans+=max(0,min(lmax[i-1],rmax[i+1])-height[i]);
}return ans;*/
int l=0,r=nums.size()-1,lmax=nums[0],rmax=nums[nums.size()-1];
int ans=0;
while(l<=r){
if(lmax<=rmax){ans+=max(0,lmax-nums[l]);lmax=max(lmax,nums[l]);l++;
}else{ans+=max(0,rmax-nums[r]);rmax=max(rmax,nums[r]); r--;
}}
return ans;}};

与上一题类似,但是更麻烦些

双指针解法

class Solution {
public:int largestRectangleArea(vector<int>& heights) {vector<int> minLeftIndex(heights.size());vector<int> minRightIndex(heights.size());int size = heights.size();// 记录每个柱子 左边第一个小于该柱子的下标minLeftIndex[0] = -1; // 注意这里初始化,防止下面while死循环for (int i = 1; i < size; i++) {int t = i - 1;// 这里不是用if,而是不断向左寻找的过程while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];minLeftIndex[i] = t;}// 记录每个柱子 右边第一个小于该柱子的下标minRightIndex[size - 1] = size; // 注意这里初始化,防止下面while死循环for (int i = size - 2; i >= 0; i--) {int t = i + 1;// 这里不是用if,而是不断向右寻找的过程while (t < size && heights[t] >= heights[i]) t = minRightIndex[t];minRightIndex[i] = t;}// 求和int result = 0;for (int i = 0; i < size; i++) {int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);result = max(sum, result);}return result;}
};

单调栈解法

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int result = 0;stack<int> st;heights.insert(heights.begin(), 0); // 数组头部加入元素0heights.push_back(0); // 数组尾部加入元素0st.push(0);// 第一个元素已经入栈,从下标1开始for (int i = 1; i < heights.size(); i++) {if (heights[i] > heights[st.top()]) { // 情况一st.push(i);} else if (heights[i] == heights[st.top()]) { // 情况二st.pop(); // 这个可以加,可以不加,效果一样,思路不同st.push(i);} else { // 情况三while (!st.empty() && heights[i] < heights[st.top()]) { // 注意是whileint mid = st.top();st.pop();if (!st.empty()) {int left = st.top();int right = i;int w = right - left - 1;int h = heights[mid];result = max(result, w * h);}}st.push(i);}}return result;}
};

相关文章:

代码随想录第46期 单调栈

这道题主要是单调栈的简单应用 class Solution { public:vector<int> dailyTemperatures(vector<int>& T) {vector<int> result(T.size(),0);stack<int> st;st.push(0);for(int i1;i<T.size();i){if(T[i]<T[st.top()]){st.push(i);}else{wh…...

中仕公考怎么样?事业编面试不去有影响吗?

事业编考试笔试已经通过&#xff0c;但是面试不去参加会有影响吗&#xff1f; 1. 自动放弃面试资格&#xff1a;未能按时出席事业单位的面试将被视为主动放弃该岗位的竞争机会。 2. 个人信誉问题&#xff1a;面试作为招聘流程的关键步骤&#xff0c;无故缺席可能被解释为诚信…...

OMV7 树莓派 tf卡安装

​ 升级7之后&#xff0c;问题多多&#xff0c;不是docker不行了&#xff0c;就是代理不好使 今天又重装了一遍&#xff0c;用官方的链接&#xff0c;重新再折腾一遍…… 使用raspberry pi imager安装最新版lite OS。 注意是无桌面 Lite版 配置好树莓派初始化设置&#xff0…...

Go语言24小时极速学习教程(五)Go语言中的SpringMVC框架——Gin

作为一个真正能用的企业级应用&#xff0c;怎么能缺少RESTful接口呢&#xff1f;所以我们需要尝试在Go语言环境中写出我们的对外接口&#xff0c;这样前端就可以借由Gin框架访问我们数据库中的数据了。 一、Gin框架的使用 1. 安装 Gin 首先&#xff0c;你需要在你的 Go 项目…...

【汇编】c++游戏开发

由一起学编程创作的‘C/C项目实战&#xff1a;2D射击游戏开发&#xff08;简易版&#xff09;&#xff0c; 440 行源码分享来啦~’&#xff1a; C/C项目实战&#xff1a;2D射击游戏开发&#xff08;简易版&#xff09;&#xff0c; 440 行源码分享来啦~_射击c-CSDN博客文章浏览…...

Android Studio | 修改镜像地址为阿里云镜像地址,启动App

在项目文件的目录下的 settings.gradle.kts 中修改配置&#xff0c;配置中包含插件和依赖项 pluginManagement {repositories {maven { urluri ("https://www.jitpack.io")}maven { urluri ("https://maven.aliyun.com/repository/releases")}maven { urlu…...

Rocky linux8 安装php8.0

Rocky linux8 安装php8.0 1.安装remi源2.列出php版本3.变更php版本&#xff0c;Rocky8有提供php8版本&#xff0c;所以切换Rocky8提供的版本&#xff0c;而不是remi提供的版本&#xff0c;不过remi有提供php8.1和php8.2版本。4.切换成remi提供的8.0版本5.安装phpendl 1.安装rem…...

Ubuntu 18 EDK2 环境编译

视频&#xff1a;在全新的Ubuntu上从零搭建UEFI的EDK2开发环境 开始&#xff1a;git clone https://github.com/tianocore/edk2.git 开始编译BaseTools前先更新一下子模块&#xff1a;git submodule update --init &#xff0c;然后&#xff1a;make -C BaseTools/ 问题1&a…...

C语言项⽬实践-贪吃蛇

目录 1.项目要点 2.窗口设置 2.1mode命令 2.2title命令 2.3system函数 2.Win32 API 2.1 COORD 2.2 GetStdHandle 2.3 CONSOLE_CURSOR_INFO 2.4 GetConsoleCursorInfo 2.5 SetConsoleCursorInfo 2.5 SetConsoleCursorPosition 2.7 GetAsyncKeyState 3.贪吃蛇游戏设…...

智慧安防丨以科技之力,筑起防范人贩的铜墙铁壁

近日&#xff0c;贵州省贵阳市中级人民法院对余华英拐卖儿童案做出了一审宣判&#xff0c;判处其死刑&#xff0c;剥夺政治权利终身&#xff0c;并处没收个人全部财产。这一判决不仅彰显了法律的威严&#xff0c;也再次唤起了社会对拐卖儿童犯罪的深切关注。 余华英自1993年至2…...

Spring:IoC/DI加载properties文件

Spring框架可以通过Spring的配置文件完成两个数据源druid和C3P0的配置&#xff08;Spring&#xff1a;IOC/DI配置管理第三方bean&#xff09;&#xff0c;但是其中包含了一些问题&#xff0c;我们来分析下: 这两个数据源中都使用到了一些固定的常量如数据库连接四要素&#xf…...

Docker 篇-Docker 详细安装、了解和使用 Docker 核心功能(数据卷、自定义镜像 Dockerfile、网络)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 Docker 概述 1.1 Docker 主要组成部分 1.2 Docker 安装 2.0 Docker 常见命令 2.1 常见的命令介绍 2.2 常见的命令演示 3.0 数据卷 3.1 数据卷常见的命令 3.2 常见…...

深挖C++赋值

详解赋值 const int a 10; int b a;&a 0x000000b7c6afef34 {56496} &a 0x000000b7c6afef34 {10} 3. &b 0x000000b7c6afef54 {10} 总结&#xff1a; int a 10 是指在内存中&#xff08;栈&#xff09;中创建一个int &#xff08;4 byte&#xff09;大小的空间…...

【免越狱】iOS砸壳 可下载AppStore任意版本 旧版本IPA下载

软件介绍 下载iOS旧版应用&#xff0c;简化繁琐的抓包流程。 一键生成去更新IPA&#xff08;手机安装后&#xff0c;去除App Store的更新检测&#xff09;。 软件界面 支持系统 Windows 10/Windows 8/Windows 7&#xff08;由于使用了Fiddler库&#xff0c;因此需要.Net环境…...

【python笔记02】面向对象思想

关于面向对象要学会啥&#xff1f; 面向对象编程思想面向对象基本概念 对象类 添加和获取对象属性魔术方法&#xff08;三个常见的&#xff09;面向对象案例 面向对象编程思想 两个时代的两个产物&#xff0c;没有好坏之分&#xff0c;小系统用面向过程&#xff0c;团队开发…...

Java基础-Java多线程机制

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 一、引言 二、多线程的基本概念 1. 线程与进程 2. 多线程与并发 3. 多线程的优势 三、Java多线程的实…...

MySQL技巧之跨服务器数据查询:基础篇-A数据库与B数据库查询合并--封装到存储过程中

MySQL技巧之跨服务器数据查询&#xff1a;基础篇-A数据库与B数据库查询合并–封装到存储过程中 我们的最终目的是什么&#xff1f;当然的自动执行这些合并操作&#xff01; 上一篇 MySQL技巧之跨服务器数据查询&#xff1a;基础篇-A数据库与B数据库查询合并 我们已经知道怎么合…...

MATLAB向量元素的引用

我们定义一个向量后&#xff0c;如果想引用的话&#xff0c;可以通过索引 i n d ind ind来实现。 注意&#xff1a;MATLAB中向量的开始索引是1&#xff0c;与许多编程语言不同。 例如&#xff1a; 如果想引用多个的话&#xff0c;可以用索引 i n d ind ind来提取多个位置 例如…...

leetcode-44-通配符匹配

题解&#xff1a; 代码&#xff1a; 参考&#xff1a; (1)牛客华为机试HJ71字符串通配符 (2)leetcode-10-正则表达式匹配...

基于YOLOv8深度学习的智慧课堂学生专注度检测系统(PyQt5界面+数据集+训练代码)

本研究提出了一种基于YOLOv8深度学习的智慧课堂学生专注度检测系统&#xff0c;旨在实现对课堂中学生专注度的实时分析与评估。随着智慧教育的快速发展&#xff0c;学生的课堂表现和专注度成为评估学习效果的重要因素之一。然而&#xff0c;传统的专注度评估方法往往依赖于主观…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...