代码随想录算法训练营第五十八天| 739 每日温度 496 下一个更大元素 |
2023-12-22 18:46:47
目录
739 每日温度
求后面第一个比他大的元素的位置,单调栈如果递增
求后面第一个比他小的元素的位置,单调栈需要递减
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int> st;//求的是后面第一个比他大的元素的位置,所以单调栈需要递增
vector<int> res(temperatures.size(),0);//使得递增
st.push(0);//存放temperatures的下标
for(int i = 1;i < temperatures.size();i++){
if(temperatures[i] <= temperatures[st.top()]){
st.push(i);
}else{
while(!st.empty() && temperatures[i] > temperatures[st.top()]){//确保单调栈递增
res[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
}
return res;
}
};
时间复杂度O(n)
空间复杂度O(n)?
496 下一个更大元素 |
求后面第一个比他大的元素的位置,单调栈如果递增
求后面第一个比他小的元素的位置,单调栈需要递减
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int>st;
vector<int>res(nums1.size(),-1);
unordered_map<int,int>mp;
for(int i = 0;i < nums1.size();i++){//key:下标元素 value:下标
mp[nums1[i]] = i;//将nums1中的数据存放到mp中
}
st.push(0);//存放下标
for(int i = 1;i < nums2.size();i++){
if(nums2[i] <= nums2[st.top()]){//求后面第一个比他大的元素的位置,单调栈如果递增
st.push(i);
}else{//确保单调栈单调递增
while(!st.empty() && nums2[i] > nums2[st.top()]){//找到自己的位置才停止
if(mp.count(nums2[st.top()]) > 0){//nums1中存在这个元素
int idx = mp[nums2[st.top()]];
res[idx] = nums2[i];
}
st.pop();
}
st.push(i);
}
}
return res;
}
};
时间复杂度O(m+n)//m是nums1的长度,n是nums2的长度
空间复杂度O(n)?
文章来源:https://blog.csdn.net/m0_72832574/article/details/135133532
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!