当前位置: 首页 > 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、内存和磁盘使用…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...