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

Leecode---栈---每日温度 / 最小栈及栈和队列的相互实现

:先入后出;队列:先入先出

一、每日温度
Leecode—739题目
给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。
在这里插入图片描述
单调栈思路
1、新建一个存储数组下标的栈,将数组元素的下标依次入栈;
2、入栈的过程中,要保证栈是单调的;如果此时数组元素大于栈顶下标对应的数组元素,弹出栈顶,再将此时的下标i入栈;
3、在这个过程中,下标i挤掉栈顶下标的时候,i-stack.top(),这个值就是我们要的“下一天”;没有出现“挤掉”情况的下标,也就是最后栈中仍剩余的下标,就是未来没有更高的温度,在answer数组中对应下标为初始的0即可。

class Solution
{
public:vector<int> dailyTemperatures(vector<int>& temperatures){int n = temperatures.size();vector<int> answer(n);// 存储下标的单调栈stack<int> tmp;for(int i=0; i<n; i++){// 若栈不为空,且t[i]>栈顶while(!tmp.empty() && temperatures[i] > temperatures[tmp.top()]){// 记录栈顶的下标int top_Index = tmp.top();// 当前栈顶对应的下标,它的‘下一天’就是 i-tmp.top()answer[top_Index] = i - top_Index;tmp.pop();}// 单调栈,将小于栈底的下标入栈tmp.push(i);}return answer;}
};

二、最小栈
Leecode–155:
题目
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

class MinStack
{
public:// 定义两个栈容器stack<int> st;stack<int> minStack;// 构造函数清空栈容器MinStack(){while(!st.empty()){st.pop();}while(!minStack.empty()){minStack.pop();}// 初始化最小栈的栈顶元素为最大值,为了防止top访问空指针报错minStack.push(INT_MAX);}void push(int x){st.push(x);// 比较最小栈栈顶值和当前值x的大小,将最小值压入最小栈// 记录当前st栈的最小值为栈顶元素int minval = std::min(minStack.top(),x);minStack.push(minval);	// 最小值压入最小栈}void pop(){st.pop();minStack.pop();}int top(){return st.top();}int getMin(){// 取最小栈的栈顶元素,就是此时st栈的最小值return minStack.top();}
};

三、用队列实现栈
问题描述
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。

实现 MyStack 类:
void push(int x) 将元素 x 压入栈顶(入栈)。
int pop() 移除并返回栈顶元素(出栈)。
int top() 返回栈顶元素(取栈顶)。
boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

#include<iostream>
#include<stack>
#include<queue>
using namespace std;class MyStack
{queue<int> q;	// 定义一个队列
public:MyStack(){}void push(int x)	// 入栈{int n = q.size();q.push(x);for(int i=0; i<n; i++){q.push(q.front());	// 将队头放入队尾q.pop();			// 移除队头}}int pop()	// 出栈==出队,有返回值,记录队头->移除队头->返回所记录的队头{int t = q.front();q.pop();return t;}int top()		// 取栈顶==取队头{int t = q.front();return t;}bool empty()	// 判断栈空==判断队空{return q.empty();}
};

四、用栈实现队列
top()是取栈顶元素,不会删除里面的元素,返回栈顶的引用;
pop()是删除栈顶元素,返回void。
int peek() :返回队列开头的元素
void push(int x): 将元素x放到队列的末尾
int pop() : 从队列开头移除并返回元素
boolean empty() : 若队列为空,返回true,否则返回false

算法实现
用两个栈模拟一个队列,s1为输入栈,s2为输出栈;
1、push(x):将x放入s1;
2、pop():若s2为空,则将s1中所有的元素放入s2,s2的栈顶出栈,并返回栈顶元素;
3、peek():若s2为空,将s1中所有的元素放入s2,并返回栈顶元素;
4、empty():若s1 / s2都为空,返回true,否则返回false。

class MyQueue
{
private:stack<int> s1, s2;		// s1为输入栈,s2为输出栈void int_2_out(){// 如果输出栈为空,则将输入栈所有元素放入输出栈if (s2.empty()){while(!s1.empty()){//s1先把栈顶元素取出来放入s2,然后再pop删除,s1为空则停止s2.push(s1.top());s1.pop();}}}
public:MyQueue(){}void push(int x)	// 入队{s1.push(x);	}int pop()			// 模拟出队{// pop是从输出栈出栈int_2_out();	// 判断输出栈是否为空,若为空,将输入栈放入输出栈int x = s2.top();s2.pop();return x;		// 返回栈顶}int peek()			// 取队头操作{in_2_out();return s2.top();}bool empty()		// 栈 s1/s2 都为空,队列才为空{return s1.empty() && s2.empty();}
};

相关文章:

Leecode---栈---每日温度 / 最小栈及栈和队列的相互实现

栈&#xff1a;先入后出&#xff1b;队列&#xff1a;先入先出 一、每日温度 Leecode—739题目&#xff1a; 给定一个整数数组 temperatures &#xff0c;表示每天的温度&#xff0c;返回一个数组 answer &#xff0c;其中 answer[i] 是指对于第 i 天&#xff0c;下一个更高温…...

Linux系统编程——动静态库

目录 一&#xff0c;关于动静态库 1.1 什么是库&#xff1f; 1.2 认识动静态库 1.3 动静态库特征 二&#xff0c;静态库 2.1 制作静态库 2.2 使用静态库 三&#xff0c;动态库 3.1 制作动态库 3.2 使用动态库一些问题 3.3 正确使用动态库三种方法 3.3.1 方法一&…...

json formatter哪个好用

在众多的JSON Formatter工具中&#xff0c;确实有几个相当出色的选择&#xff0c;它们各自拥有独特的特点和优势&#xff0c;可以满足不同用户群体的需求。下面就来为大家推荐几个好用的JSONFormatter工具&#xff1a; 1. JSON Formatter & Validator&#xff1a;这款工具…...

react的hooks是什么意思

React Hooks 是 React 16.8 版本引入的一个新特性&#xff0c;它允许你在不编写类组件的情况下使用状态和其他React特性。Hooks使得函数组件变得更加灵活和强大&#xff0c;因为你可以在其中添加状态逻辑、生命周期方法以及其他React功能。 在传统的React类组件中&#xff0c;…...

AVFrame相关接口(函数)

分配和释放 分配 AVFrame AVFrame *av_frame_alloc(void); 分配一个新的 AVFrame 并返回一个指向它的指针。返回的 AVFrame 需要手动释放。 释放 AVFrame void av_frame_free(AVFrame **frame); 释放由 av_frame_alloc 分配的 AVFrame。这个函数会释放帧的数据并将指针设为 …...

低代码与人工智能的深度融合:行业应用的广泛前景

引言 在当今快速变化的数字化时代&#xff0c;企业面临着越来越多的挑战和机遇。低代码平台和人工智能技术的兴起&#xff0c;为企业提供了新的解决方案&#xff0c;加速了应用开发和智能化转型的步伐。 低代码平台的基本概念及发展背景 低代码平台是一种软件开发方法&#x…...

嵌入式测试基础知识

1.白盒测试也称为结构测试&#xff0c;主要用于检测软件编码过程中的错误。 2.黑盒测试又称为功能测试&#xff0c;主要检测软件的每一个功能是否能够正常使用。 3.软件测试流程&#xff1a;根据测试需求编写测试计划、方案&#xff0c;测试用例&#xff0c;做测试分析&#…...

基于网关的ip频繁访问web限制

一、前言 外部ip对某一个web进行频繁访问&#xff0c;有可能是对web进行攻击&#xff0c;现在提供一种基于网关的ip频繁访问web限制策略&#xff0c;犹如带刀侍卫&#xff0c;审查异常身份人员。如发现异常或者暴力闯关者&#xff0c;即可进行识别管制。 二、基于网关的ip频繁访…...

GSM信令流程(附着、去附着、PDP激活、修改流程)

1、联合附着流程 附着包括身份认证、鉴权等 2、去附着流程 用户发起去附着 SGSN发起去附着 HLR发起去附着 GSSN使用S4发起去附着 3、Activation Procedures(PDP激活流程) 4、PDP更新或修改流程 5、Deactivate PDP Context 6、RAU(Routeing Area Update)流程 7、鉴权加…...

OAK相机如何将 YOLOv10 模型转换成 blob 格式?

编辑&#xff1a;OAK中国 首发&#xff1a;oakchina.cn 喜欢的话&#xff0c;请多多&#x1f44d;⭐️✍ 内容可能会不定期更新&#xff0c;官网内容都是最新的&#xff0c;请查看首发地址链接。 Hello&#xff0c;大家好&#xff0c;这里是OAK中国&#xff0c;我是Ashely。 专…...

【Python】解决Python报错:AttributeError: ‘class‘ object has no attribute ‘xxx‘

&#x1f9d1; 博主简介&#xff1a;阿里巴巴嵌入式技术专家&#xff0c;深耕嵌入式人工智能领域&#xff0c;具备多年的嵌入式硬件产品研发管理经验。 &#x1f4d2; 博客介绍&#xff1a;分享嵌入式开发领域的相关知识、经验、思考和感悟&#xff0c;欢迎关注。提供嵌入式方向…...

反思 GTC 和 OFC 2024:没有一刀切的方法,但上市时间是关键!

在GTC 2024期间&#xff0c;英伟达宣布了最新的Blackwell B200张量核心GPU&#xff0c;旨在为万亿参数的AI大型语言模型提供支持。Blackwell B200需要先进的800Gbps网络&#xff0c;完全符合在AI工作负载的AI网络报告中概述的预测。随着人工智能工作负载的流量预计每两年增长10…...

速盾:bgp 静态 cdn

BGP&#xff08;边界网关协议&#xff09;是一种用于在互联网中交换路由信息的协议&#xff0c;它允许不同自治系统&#xff08;AS&#xff09;之间的路由器进行通信和交换路由信息。CDN&#xff08;内容分发网络&#xff09;是一种通过将内容分散放置在全球各地的服务器上&…...

union all 以及标量子查询执行计划

SELECT 1, (SELECT ID1 FROM TE WHERE IDA.ID2) FROM .TA A WHERE COLA X UNION ALL SELECT 1, (SELECT ID2 FROM TD WHERE IDA.ID1) FROM .TB A WHERE COLA X UNION ALL SELECT 1,COL2 AS PARENT_UUID FROM .TC a WHERE COLA X 三个union all 看着像是5个table joi…...

上位机图像处理和嵌入式模块部署(f103 mcu和Qt上位机联动)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 之前我们写过一篇文章&#xff0c;上面说的是如何利用串口对mcu进行控制&#xff0c;即如果利用串口实现mcu led灯的点亮和熄灭。输入1的时候&…...

TiKV学习5:TiDB SQL执行流程

目录 1. DML语句读流程概要 2. DML语句写流程概要 3. DDL 流程概要 4. SQL的Parse和Compile 5. 读取的执行 6. 写入的执行 7. DDL的执行 8. 小结 1. DML语句读流程概要 TiDB Server接收sql并处理&#xff0c;TiKV负责持久化数据&#xff0c;PD提供TSO和Region的数据字典…...

Unity 自定义编辑器根据枚举值显示变量

public class Test : MonoBehaviour {[HideInInspector][Header("数量")][SerializeField]public int num;[Header("分布类型")][SerializeField]public DistributionType distType;[HideInInspector][Header("位置")][SerializeField]public Li…...

linux下 搭建Llama3

安装软件&#xff1a; Ollama&#xff0c;官方网站&#xff1a;https://ollama.com/ 可以再下载win、mac和linux版本 linux安装命令为&#xff1a;curl -fsSL https://ollama.com/install.sh | sh 由于我的机器是linux不联网机器&#xff0c;网上没找到下载离线方式&#xff0c…...

【蓝桥杯——物联网设计与开发】拓展模块2 - 电位器模块

一、电位器模块 &#xff08;1&#xff09;资源介绍 &#x1f505;原理图 蓝桥杯物联网竞赛实训平台提供了一个拓展接口 CN2&#xff0c;所有拓展模块均可直接安装在 Lora 终端上使用&#xff1b; 图1 拓展接口 电位器模块电路原理图如下所示&#xff1a; 图2 …...

Jtti:租用的php服务器运行异常是什么原因导致的?

PHP服务器运行异常可能由多种原因引起。以下是一些常见问题及其相应的解决方案&#xff1a; 1. 服务器资源不足 原因&#xff1a; CPU、内存或磁盘空间不足&#xff0c;导致服务器性能下降。 解决方案&#xff1a; 检查系统资源&#xff1a;使用以下命令检查CPU、内存和磁盘使用…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

02.运算符

目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&&#xff1a;逻辑与 ||&#xff1a;逻辑或 &#xff01;&#xff1a;逻辑非 短路求值 位运算符 按位与&&#xff1a; 按位或 | 按位取反~ …...

虚幻基础:角色旋转

能帮到你的话&#xff0c;就给个赞吧 &#x1f618; 文章目录 移动组件使用控制器所需旋转&#xff1a;组件 使用 控制器旋转将旋转朝向运动&#xff1a;组件 使用 移动方向旋转 控制器旋转和移动旋转 缺点移动旋转&#xff1a;必须移动才能旋转&#xff0c;不移动不旋转控制器…...

基于 HTTP 的单向流式通信协议SSE详解

SSE&#xff08;Server-Sent Events&#xff09;详解 &#x1f9e0; 什么是 SSE&#xff1f; SSE&#xff08;Server-Sent Events&#xff09; 是 HTML5 标准中定义的一种通信机制&#xff0c;它允许服务器主动将事件推送给客户端&#xff08;浏览器&#xff09;。与传统的 H…...