【代码随想录】【算法训练营】【第53天】 [739]每日温度 [496]下一个更大元素I [503]下一个更大元素II

前言

思路及算法思维,指路 代码随想录。
题目来自 LeetCode。

day 48,周六,不能再坚持~

题目详情

[739] 每日温度

题目描述

739 每日温度
739 每日温度

解题思路

前提:寻找任一个元素的右边比自己大的元素的位置
思路:通常是一维数组,要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,此时可以用单调栈,使用空间换时间
重点:单调栈的实现思维

代码实现

C语言
单调栈
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) {int *ans = (int *)malloc(sizeof(int) * temperaturesSize);int stack[temperaturesSize];int top = 0;memset(ans, 0, sizeof(int) * temperaturesSize);memset(stack, 0, sizeof(stack));for (int i = 0; i < temperaturesSize; i++) {while (top > 0 && temperatures[i] > temperatures[stack[top - 1]]) {// 当前元素 大于 栈顶元素,找到栈顶元素的右侧第一个更高温度ans[stack[top - 1]] = i - stack[top - 1];top--;}stack[top] = i;top++;}*returnSize = temperaturesSize;return ans;
}

[496] 下一个更大元素I

题目描述

496 下一个更大元素I
496 下一个更大元素I

解题思路

前提:寻找另一数组中相同元素的右侧第一个比其大的值
思路:对nums2使用单调栈,再利用哈希对nums1中元素赋值
重点:单调栈的实现思维

代码实现

C语言
单调栈
/*** Note: The returned array must be malloced, assume caller calls free().*/
#define NUM_MAX_SIZE 10001
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {int *ans = (int *)malloc(sizeof(int) * nums1Size); int map[NUM_MAX_SIZE];memset(map, -1, sizeof(map));for (int i = 0; i < nums1Size; i++) {ans[i] = -1;map[nums1[i]] = 0;}// 对nums2使用单调栈int stack[NUM_MAX_SIZE];memset(stack, -1, sizeof(stack));int top = 0;for (int i = 0; i < nums2Size; i++) {while (top > 0 && nums2[i] > nums2[stack[top - 1]]) {// 当前元素大于栈顶元素,找到栈顶元素右侧的第一个更大元素map[nums2[stack[top - 1]]] = nums2[i];top--;}stack[top] = i;top++;}// 赋值结果for (int i = 0; i < nums1Size; i++) {if (map[nums1[i]] > 0) {ans[i] = map[nums1[i]];} else {ans[i] = -1;}}*returnSize = nums1Size;return ans;
}

[503] 下一个更大元素II

题目描述

503 下一个更大元素II
503 下一个更大元素II

解题思路

前提:寻找同一数组中相同元素的右侧第一个比其大的值,可循环查找
思路:循环两次对nums使用单调栈
重点:单调栈的实现思维

代码实现

C语言
单调栈
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* nextGreaterElements(int* nums, int numsSize, int* returnSize) {int *ans = (int *)malloc(sizeof(int) * numsSize);memset(ans, -1, sizeof(int) * numsSize);// 单调栈int stack[numsSize * 2];int top = 0;memset(stack, 0, sizeof(stack));for (int i = 0; i < numsSize * 2; i++) {while (top > 0 && nums[i % numsSize] > nums[stack[top - 1]]) {// 找到第一个比栈顶元素大的数值ans[stack[top - 1]] = nums[i % numsSize];top--;}stack[top] = i % numsSize;top++;}*returnSize = numsSize;return ans;
}

今日收获

  1. 单调栈

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/368358.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

(三十一)Flask之wtforms库【剖析源码下篇】

每篇前言&#xff1a; &#x1f3c6;&#x1f3c6;作者介绍&#xff1a;【孤寒者】—CSDN全栈领域优质创作者、HDZ核心组成员、华为云享专家Python全栈领域博主、CSDN原力计划作者 &#x1f525;&#x1f525;本文已收录于Flask框架从入门到实战专栏&#xff1a;《Flask框架从入…

spring boot初始化的几个总结

spring intializr File->New->Project 注意&#xff1a;Spring Initializer中 Java版本选择模块已经不支持1.8了。 Spring Boot 3.x要求 Java最低版本为17&#xff0c; 最新的SpringBoot版本已经要求Java22了 所以&#xff0c;你可以升级Java版本&#xff0c;使用Spri…

6.26.3 基于Transformer的深度神经网络在数字乳腺断层合成图像上的乳腺癌分类

开发一种有效的深度神经网络模型&#xff0c;该模型结合了相邻图像部分的上下文&#xff0c;以检测数字乳腺断层合成(DBT)图像上的乳腺癌。 数字乳房断层合成(DBT)是一种医学成像技术&#xff0c;其中检测器围绕患者以有限角度旋转并记录多幅图像。然后将这些图像重建为二维(2D…

【Python】变量与基本数据类型

个人主页&#xff1a;【&#x1f60a;个人主页】 系列专栏&#xff1a;【❤️Python】 文章目录 前言变量声明变量变量的命名规则 变量赋值多个变量赋值 标准数据类型变量的使用方式存储和访问数据&#xff1a;参与逻辑运算和数学运算在函数间传递数据构建复杂的数据结构 NameE…

关于5G和卫星

手机&#xff0c;已经串联起了我们生活中的一切环节。我们随时随地拿出手机&#xff0c;都能畅快地上网。 这一切是如此地理所当然&#xff0c;以至于我们甚至想不到这样不可思议的问题&#xff1a; 移动通信网络真的无处不在吗&#xff1f; 我们都知道&#xff0c;地球虽叫…

WordPress主题大前端DUX v8.7源码下载

全新&#xff1a;用户注册流程&#xff0c;验证邮箱&#xff0c;设置密码 新增&#xff1a;列表显示小视频和横幅视频 新增&#xff1a;文章内容中的外链全部增加 nofollow 新增&#xff1a;客服功能中的链接添加 nofollow 优化&#xff1a;产品分类的价格显示

Day05-讲师列表前端-讲师信息添加

代码&#xff1a; //添加讲师 addTeacher(teacher){ return request({ url:/eduservice/teacher/addTeacher, method:‘post’, data:teacher }) } &#xff08;2&#xff09;在页面实现调用 代码&#xff1a; 讲师添加 <el-button type“primary” :disabled“sav…

【Qt之·类QVariant·数据类型】

系列文章目录 文章目录 前言一、概述二、操作及用法1.1 存储数据1.2 获取数据1.3 设置数据1.4 数据类型判断1.5 判断数据是否有效 三、实例演示总结 前言 QVariant是Qt开发中非常重要的一部分&#xff0c;它是Qt的一个核心类&#xff0c;用于处理不同数据类型之间的转换和传递。…

Elasticsearch集群部署(下)

目录 上篇&#xff1a;Elasticsearch集群部署&#xff08;上&#xff09;-CSDN博客 七. Filebeat 部署 八. 部署Kafka 九. 集群测试 链接&#xff1a;https://pan.baidu.com/s/1AFXSmDdY5xBb7g35ipKoaw?pwdfa9m 提取码&#xff1a;fa9m 七. Filebeat 部署 为什么用 F…

使用 draw.io 画图

尽管我非常喜欢 wps 和 office 的 ppt 画图&#xff0c;但因为它们对数学公式的糟糕支持&#xff0c;我不得不另外寻找一个画图工具。当然我也同样很喜欢 visio &#xff0c;但同样的&#xff0c;它对数学公式的支持糟糕&#xff0c;另外&#xff0c;最为重要的是&#xff0c;v…

java设计模式(十二)享元模式(Flyweight Pattern)

1、模式介绍&#xff1a; 享元模式是一种结构型设计模式&#xff0c;旨在通过共享对象来有效支持大量细粒度的对象。它通过将对象的状态分为内部状态&#xff08;可共享&#xff09;和外部状态&#xff08;不可共享&#xff09;来减少内存消耗和提高性能。内部状态存储在享元对…

​Chrome插件:React Developer Tools为React开发调试而生

React Developer Tools 是什么? 它是允许在Chrome和Firefox开发者工具中检查React组件层次结构的扩展插件。 插件源码下载 源码下载地址:GitHub - facebook/react-devtools at v3 下载完成以后执行红框中的代码,下载react-devtools 源码,源码如下图所示: 插件打包 当前n…

【软件测试】如何搭建appium工具环境?

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 1、安装Java Development Kit&#xff08;JDK&#xff09; 前往Oracle官网下载JDK。 在https:/…

用Python制作动态钟表:实时显示时间的动画

文章目录 引言准备工作前置条件 代码实现与解析导入必要的库初始化Pygame绘制钟表函数主循环 完整代码 引言 动态钟表是一种直观且实用的UI元素&#xff0c;能够实时显示当前时间。在这篇博客中&#xff0c;我们将使用Python创建一个动态钟表&#xff0c;通过利用Pygame库来实…

高校搭建AIGC新媒体实验室,创新新闻教育教学模式

高校作为人才培养的重要阵地&#xff0c;必须紧跟时代步伐&#xff0c;不断创新教育教学模式&#xff0c;提升跨界融合育人水平&#xff0c;通过AIGC新媒体实验室探索创新人才培养模式。AIGC新媒体实验室不仅能够高效赋能高校宣传媒体矩阵&#xff0c;也可以助力教学实践与AIGC…

【设计模式】观察者模式(定义 | 特点 | Demo入门讲解)

文章目录 定义结构Demo | 代码Subject目标类Observer抽象观察者观察者1 | CPU监听器观察者2 | 内存监听器客户端 | Client 优点适合场景 定义 所谓观察者模式就是你是被观察的那个对象&#xff0c;你爸爸妈妈就是观察者&#xff0c;一天24h盯着你&#xff0c;一旦你不听话&…

使用requests爬取拉勾网python职位数据

爬虫目的 本文是想通过爬取拉勾网Python相关岗位数据&#xff0c;简单梳理Requests和xpath的使用方法。 代码部分并没有做封装&#xff0c;数据请求也比较简单&#xff0c;所以该项目只是为了熟悉requests爬虫的基本原理&#xff0c;无法用于稳定的爬虫项目。 爬虫工具 这次…

目标和问题:从回溯到动态规划的旅程

目录 引言 题目描述 示例 初步思路&#xff1a;回溯法 回溯法实现 分析 转变思路&#xff1a;动态规划 问题转换 状态定义 状态转移方程 二维动态规划实现 压缩到一维动态规划 一维动态规划实现 详细讲解&#xff1a;从回溯到动态规划的旅程 1. 从回溯到动态规划…

【java计算机毕设】美容院管理系统 项目源代码MySQL springboot vue html maven+文档 前后端可分离也可不分离

目录 1项目功能 2项目介绍 3项目地址 1项目功能 【java计算机毕设】美容院管理系统 项目源代码MySQL springboot vue html maven文档 前后端可分离也可不分离 2项目介绍 系统功能&#xff1a; 美容院管理系统包括管理员、用户俩种角色。 管理员功能包括个人中心模块用于修改…

YOLO-letter box

最细致讲解yolov8模型推理完整代码--&#xff08;前处理&#xff0c;后处理&#xff09; - 博客-中国极客 (chinageek.org) 直接用resize&#xff0c;图片会变形&#xff0c;宽高比会不对 letterbox函数就是把图片弄到想要的大小&#xff0c;保持宽高比&#xff0c;然后少掉的部…