C++ day58 每日温度 下一个更大元素

2023-12-08 06:45

本文主要是介绍C++ day58 每日温度 下一个更大元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目1:739 每日温度

题目链接:每日温度

对题目的理解

temperature[i]表示每天的温度,返回数组answer,answer[i]指对于第i天,下一个更高温度最近出现在几天后,如果气温在这之后都不会升高,用0来代替

暴力解法

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> answer(temperatures.size(),0);for(int i=0;i<temperatures.size();i++){for(int j=i+1;j<temperatures.size();j++){if(temperatures[j]>temperatures[i]){answer[i]=j-i;break;} }}return answer;}
};

会报超时错误

单调栈

1)何时想到使用单调栈?

通常是一维数组,要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,此时我们就要想到可以用单调栈了,时间复杂度为O(n)

单调栈的本质是空间换时间,因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素,优点是整个数组只需要遍历一次。

就是用一个栈来记录已经遍历过的元素

2)如何使用单调栈?

单调栈里只需要存放元素的下标i就可以了,如果需要使用对应的元素,直接T[i]就可以获取。

只有递增的时候,栈里要加入一个元素i的时候,才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。

使用单调栈主要有三个判断条件。

  • 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
  • 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
  • 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

整个流程

定义result数组的时候,就应该直接初始化为0,如果result没有更新,说明这个元素右面没有更大的了,也就是为0。

伪代码

代码

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> result(temperatures.size(),0);stack<int> st;st.push(0);for(int i=1;i<temperatures.size();i++){if(temperatures[i]<temperatures[st.top()]) st.push(i);else if(temperatures[i]==temperatures[st.top()]) st.push(i);else {while(!st.empty() && temperatures[i]>temperatures[st.top()]){result[st.top()] = i-st.top();st.pop();}st.push(i);}}return result;      }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

精简代码

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> result(temperatures.size(),0);stack<int> st;st.push(0);for(int i=1;i<temperatures.size();i++){while(!st.empty() && temperatures[i]>temperatures[st.top()]){result[st.top()]=i-st.top();st.pop();}if(temperatures[i]<=temperatures[st.top()]) st.push(i);}return result;      }
};

上述代码会出现如下错误

原因是for循环中下面的if判断并没有限制st,若st可能出现空栈的情况

将代码改正如下:

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> result(temperatures.size(),0);stack<int> st;st.push(0);for(int i=1;i<temperatures.size();i++){while(!st.empty() && temperatures[i]>temperatures[st.top()]){result[st.top()]=i-st.top();st.pop();}if(!st.empty() && temperatures[i]<=temperatures[st.top()]) st.push(i);}return result;      }
};

这个时候倒是不报执行错误了,又有新的错误产生了,案例错误

出现这种错误的原因是在while循环中,栈外元素大于栈顶元素的情况,在栈顶元素弹出之后并没有将新的元素放入堆栈,因此将代码修改如下

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> result(temperatures.size(),0);stack<int> st;st.push(0);for(int i=1;i<temperatures.size();i++){while(!st.empty() && temperatures[i]>temperatures[st.top()]){result[st.top()]=i-st.top();st.pop();st.push(i);}if(!st.empty() && temperatures[i]<=temperatures[st.top()]) st.push(i);}return result;      }
};

又有新的错误出现了

原因是while循环代表着,栈外元素一直比栈顶元素大,那么一直弹出栈顶元素,直到小于等于为止,这个过程不应该将栈外元素放入堆栈,将栈外元素放入堆栈的操作应在整个while循环都遍历完成后才进行,因此,可以将代码改为如下,因为栈外元素大于等于栈顶元素的时候,一定是要放入堆栈的,所以这两步操作可以合并起来,就是没有这个if限制条件了,只要不满足栈外元素大于栈顶元素了,就将栈外元素放入堆栈,这时代码才可以正常通过·

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> result(temperatures.size(),0);stack<int> st;st.push(0);for(int i=1;i<temperatures.size();i++){while(!st.empty() && temperatures[i]>temperatures[st.top()]){result[st.top()]=i-st.top();st.pop();}st.push(i);}return result;      }
};

题目2:496 下一个更大元素Ⅰ

题目链接:下一个更大元素Ⅰ

对题目的理解

两个数组nums1和nums2无重复元素,nums1是nums2的子集,找满足nums1[i]==nums2[j]的下标j,(即在数组nums2中,找出与nums1中相同元素的下标),并在nums2确定nums2[j]的下一个更大元素,如果不存在,则返回1

nums1中x的下一个更大元素是指:x在nums2中对应位置右侧的第一个比x大的元素

nums1和nums2至少包含一个元素

常规思路

常规思路,求出nums1中的元素在nums2中相等的下标,然后根据这个下标数组遍历nums2进行查找,但是卡死了,一直报错误

代码(卡死了)

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {       vector<int> index(nums1.size(),0);for(int i=0;i<nums1.size();i++){for(int j=0;j<nums2.size();j++){if(nums1[i]==nums2[j]) index.push_back(j);}//使用index存储nums2中的下标4,7,8,9}vector<int> result(nums1.size(),-1);stack<int> st;for(int i=0;i<index.size();i++){while(!st.empty() && nums2[index[i]]>nums2[st.top()]){result[]=nums2[index[i]];st.pop();}st.push(index[i]);}return result;}
};

单调栈

注意题目中说是两个没有重复元素 的数组 nums1 和 nums2,没有重复元素,就可以用map来做映射了。根据数值快速找到下标,还可以判断nums2[i]是否在nums1中出现过,C++中,使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的

分析如下三种情况:

情况一:当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况,此时满足递增栈(栈头到栈底的顺序),所以直接入栈。

情况二:当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况,如果相等的话,依然直接入栈,求的是右边第一个比自己大的元素,而不是大于等于!

情况三:当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况,判断栈顶元素是否在nums1里出现过,(注意栈里的元素是nums2的元素),如果出现过,开始记录结果。

伪代码

代码(注意一定要是nums2[st.top()]

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {       vector<int> result(nums1.size(),-1);//初始化为-1stack<int> st;//定义一个哈希表,来映射nums1的元素与下标的关系unordered_map<int,int> umap;for(int i=0;i<nums1.size();i++){umap[nums1[i]]=i;//元素  位置,后续nums2根据与nums1中相同的元素,找到该位置i,更新该处的数值}st.push(0);for(int i=1;i<nums2.size();i++){while(!st.empty() && nums2[i]>st.top()){//如果出现元素大于的情况//如果这个元素在nums1中if(umap.count(st.top())>0){int index=umap[st.top()];//获取这个元素在的位置,最上面for循环的iresult[index]=nums2[i];}st.pop();}st.push(nums2[i]);}return result;}
};

!!!注意st栈中放的是下标,是下标,是下标,重要的事情说三遍,使用的时候需要将该下标带入数组,一定要是nums2[st.top()],将代码改为如下就OK

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {       vector<int> result(nums1.size(),-1);//初始化为-1stack<int> st;//定义一个哈希表,来映射nums1的元素与下标的关系unordered_map<int,int> umap;for(int i=0;i<nums1.size();i++){umap[nums1[i]]=i;//元素  位置,后续nums2根据与nums1中相同的元素,找到该位置i,更新该处的数值}st.push(0);for(int i=1;i<nums2.size();i++){if(nums2[i]<nums2[st.top()]) st.push(i);else if(nums2[i]==nums2[st.top()]) st.push(i);else {while(!st.empty() && nums2[i]>nums2[st.top()]){//如果出现元素大于的情况//如果这个元素在nums1中if(umap.count(nums2[st.top()])>0){int index=umap[nums2[st.top()]];//获取这个元素在的位置,最上面for循环的iresult[index]=nums2[i];}st.pop();}st.push(i);}}return result;}
};

精简代码

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {       vector<int> result(nums1.size(),-1);//初始化为-1stack<int> st;//定义一个哈希表,来映射nums1的元素与下标的关系unordered_map<int,int> umap;for(int i=0;i<nums1.size();i++){umap[nums1[i]]=i;//元素  位置,后续nums2根据与nums1中相同的元素,找到该位置i,更新该处的数值}st.push(0);for(int i=1;i<nums2.size();i++){while(!st.empty() && nums2[i]>nums2[st.top()]){//如果出现元素大于的情况//如果这个元素在nums1中if(umap.count(nums2[st.top()])>0){int index=umap[nums2[st.top()]];//获取这个元素在的位置,最上面for循环的iresult[index]=nums2[i];}st.pop();}st.push(i);}return result;}
};

这篇关于C++ day58 每日温度 下一个更大元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/468912

相关文章

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

从入门到精通C++11 <chrono> 库特性

《从入门到精通C++11<chrono>库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段(Durat

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多,因为它实际属于c++20最为重要的

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

C++11委托构造函数和继承构造函数的实现

《C++11委托构造函数和继承构造函数的实现》C++引入了委托构造函数和继承构造函数这两个重要的特性,本文主要介绍了C++11委托构造函数和继承构造函数的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、委托构造函数1.1 委托构造函数的定义与作用1.2 委托构造函数的语法1.3 委托构造函

C++11作用域枚举(Scoped Enums)的实现示例

《C++11作用域枚举(ScopedEnums)的实现示例》枚举类型是一种非常实用的工具,C++11标准引入了作用域枚举,也称为强类型枚举,本文主要介绍了C++11作用域枚举(ScopedEnums... 目录一、引言二、传统枚举类型的局限性2.1 命名空间污染2.2 整型提升问题2.3 类型转换问题三、C

C++链表的虚拟头节点实现细节及注意事项

《C++链表的虚拟头节点实现细节及注意事项》虚拟头节点是链表操作中极为实用的设计技巧,它通过在链表真实头部前添加一个特殊节点,有效简化边界条件处理,:本文主要介绍C++链表的虚拟头节点实现细节及注... 目录C++链表虚拟头节点(Dummy Head)一、虚拟头节点的本质与核心作用1. 定义2. 核心价值二

python3如何找到字典的下标index、获取list中指定元素的位置索引

《python3如何找到字典的下标index、获取list中指定元素的位置索引》:本文主要介绍python3如何找到字典的下标index、获取list中指定元素的位置索引问题,具有很好的参考价值,... 目录enumerate()找到字典的下标 index获取list中指定元素的位置索引总结enumerat