当前位置: 首页 > 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;传统的专注度评估方法往往依赖于主观…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...