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

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...