本文主要是介绍代码随想录算法训练营29期Day61|LeetCode 739,496,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文档讲解:每日温度 下一个更大元素I
739.每日温度
题目链接:https://leetcode.cn/problems/daily-temperatures/description/
思路:
维护一个单调递减的栈就行了。
一次读取一个数组中的元素,将其与栈顶元素比较,如果比栈顶元素大,证明找到了栈顶元素右侧第一个比它大的,记录并弹出栈顶即可。
重复上述比较直至该元素小于栈顶元素或者栈空。
加入这个元素即可。
重复上述操作可解决问题。
核心代码:
class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {stack<int> st;int n=temperatures.size();vector<int> ans(n,0);for(int i=0;i<n;i++){while(!st.empty()&&temperatures[st.top()]<temperatures[i]){ans[st.top()]=i-st.top();st.pop();}st.push(i);}return ans;}
};
496.下一个更大元素I
题目链接:https://leetcode.cn/problems/next-greater-element-i/description/
思路:
这题有O()的做法,就是枚举nums1中的数字,去nums2中遍历找到其位置,然后再向后找第一个比它大的值即可。
这种方法很简单,也能过这道题数据范围,但不在此赘述。
下面阐述一种O(n)的做法:
对nums2使用单调栈,维护一个单调递减的序列(详情见上一道题目),由此可得到nums2中每个值右侧的第一个比它大的值,记为map。
然后遍历nums1,根据map确定nums1中的值的下一个更大元素,获得答案数组输出即可。
核心代码:
class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {map<int,int> mp;stack<int> st;int n=nums2.size();vector<int> ans(nums1.size(),-1);for(int i=0;i<n;i++){while(!st.empty()&&nums2[st.top()]<nums2[i]){mp[nums2[st.top()]]=nums2[i];st.pop();}st.push(i);}while(!st.empty()){mp[nums2[st.top()]]=-1;st.pop();}n=nums1.size();for(int i=0;i<n;i++) ans[i]=mp[nums1[i]];return ans;}
};
今日总结
这次的题学习时长1h,挺简单的。
接着论文idea,头大。
这篇关于代码随想录算法训练营29期Day61|LeetCode 739,496的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!