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

2023-12-08 06:45
文章标签 c++ 元素 每日 温度 更大 day58

本文主要是介绍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++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【C++高阶】C++类型转换全攻略：深入理解并高效应用

【C++高阶】C++类型转换全攻略：深入理解并高效应用

📝个人主页🌹：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” 🤡往期回顾🤡：C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝
阅读更多...
C++——stack、queue的实现及deque的介绍

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现
阅读更多...
c++的初始化列表与const成员

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量，在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员，因为执行构造函数时，类对象已经创建完成，只有类对象创建完成才能调用成员函数，构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化，该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面，主要用于给
阅读更多...
2024/9/8 c++ smart

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2