网站搭建平台,wordpress 托管,公司注册公司哪个好,苏州建设信息网文档讲解#xff1a;每日温度 下一个更大元素I 739.每日温度
题目链接#xff1a;https://leetcode.cn/problems/daily-temperatures/description/
思路#xff1a; 维护一个单调递减的栈就行了。 一次读取一个数组中的元素#xff0c;将其与栈顶元素比较#xff0c;如… 文档讲解每日温度 下一个更大元素I 739.每日温度
题目链接https://leetcode.cn/problems/daily-temperatures/description/
思路 维护一个单调递减的栈就行了。 一次读取一个数组中的元素将其与栈顶元素比较如果比栈顶元素大证明找到了栈顶元素右侧第一个比它大的记录并弹出栈顶即可。 重复上述比较直至该元素小于栈顶元素或者栈空。 加入这个元素即可。 重复上述操作可解决问题。
核心代码
class Solution {
public:vectorint dailyTemperatures(vectorint temperatures) {stackint st;int ntemperatures.size();vectorint ans(n,0);for(int i0;in;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:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) {mapint,int mp;stackint st;int nnums2.size();vectorint ans(nums1.size(),-1);for(int i0;in;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();}nnums1.size();for(int i0;in;i) ans[i]mp[nums1[i]];return ans;}
};
今日总结 这次的题学习时长1h挺简单的。 接着论文idea头大。
