Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。
🌈个人主页：主页链接
🌈算法专栏：专栏链接
我会一直往里填充内容哒！
🌈LeetCode专栏：专栏链接
目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出
🌈代码仓库：Gitee链接
🌈点击关注=收获更多优质内容🌈
目录
题目:1019. 链表中的下一个更大节点
编辑题解:
代码实现:
完结撒花：
题目:1019. 链表中的下一个更大节点
题解:
简单来说,就是找这个节点前面离他最近的,且比他大的值.
我们可以把这个链表画成这样.
那么从右向左遍历,寻找离他最近的比他大的那个数是否就可以看成:找把他挡住的那个数.
我们从后向前遍历这个链表,
然后五没有任何数挡住他,则放入0 ans:[0]
一被五挡住了,所以一最近的比他大的数为五 ans:[0,5]
二也被五挡住了,所以二最近的比他大的数也为五 ans[0,5,5]
再来看一个例子:
依旧先把值的图画出来.
我们从后向前遍历这个链表,
五没有任何数挡住他,则放入0 ans:[0]
三被五挡住了,所以三最近的比他大的数为五 ans:[0,5]
四也被五挡住了,所以四最近的比他大的数也为五 ans:[0,5,5]
七没有任何数挡住他,则放入0 ans:[0,5,5,0]
二被七挡住了,所以离二最近比其大的数字为七 ans:[0,5,5,0,7]
因为我们是反向遍历的,所以最后要将ans 翻转一下就是答案ans:[7,0,5,5,0]
总结下我们这个过程,就是一个单调栈
我们将最后一个元素放入数据顶部,然后在答案数组中存入0(因为是第一个)
之后依次比较
若这个数小于顶部数据,则说明离他最近比他大的就是顶部数据.将其存入栈
若这个数大于顶部数据,则说明顶部数据需要更新了:将顶部数据依次移出,并比较一下其是否还小于这个数.若大于则说明离这个数最近的比他大的数被找到了.
则将顶部数据放入栈.
当然最开始要先将链表逆转一下 否则无法从后向前遍历.
代码实现:
class Solution {
public:
vector<int> nextLargerNodes(ListNode* head) {
ListNode*prev=NULL;
ListNode*cur=head;
vector<int>ans;
while(cur!=NULL){
ListNode*tmp=cur->next;
cur->next=prev;
prev=cur;
cur=tmp;
}
head=prev;
stack<int>st;
while(head)
{
if(st.empty())
{
ans.push_back(0);
st.push(head->val);
}
else if(head->val<st.top())
{
ans.push_back(st.top());
st.push(head->val);
}
else if(head->val>=st.top()){
while(!st.empty())
{
if(st.top()<=head->val)
st.pop();
else break;
}
if(st.empty())
ans.push_back(0);
else
ans.push_back(st.top());
st.push(head->val);
}
head=head->next;
}
reverse(ans.begin(),ans.end());
return ans;
}
};
完结撒花：
🌈本篇博客的内容【LeetCode每日一题 1019. 链表中的下一个更大节点 --单调栈】已经结束。
🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。文章来源：https://www.toymoban.com/news/detail-429550.html
🌈诸君，山顶见！文章来源地址https://www.toymoban.com/news/detail-429550.html
到了这里，关于LeetCode每日一题 1019. 链表中的下一个更大节点 --单调栈的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
