LeetCode每日一题 1019. 链表中的下一个更大节点 --单调栈

简介: 我们从后向前遍历这个链表,

Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。


🌈个人主页:主页链接


🌈算法专栏:专栏链接


    我会一直往里填充内容哒!


🌈LeetCode专栏:专栏链接


目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目,也会当天做完发出


🌈代码仓库:Gitee链接


🌈点击关注=收获更多优质内容🌈



题目:1019. 链表中的下一个更大节点


9cc00a51e4484ce58d9c8b8aa4337b43.png


题解:


简单来说,就是找这个节点前面离他最近的,且比他大的值.


我们可以把这个链表画成这样.


5db8e6b543444f3cbccb4f4e4d5a132e.jpg


那么从右向左遍历,寻找离他最近的比他大的那个数是否就可以看成:找把他挡住的那个数.

我们从后向前遍历这个链表,

然后五没有任何数挡住他,则放入0    ans:[0]

一被五挡住了,所以一最近的比他大的数为五   ans:[0,5]

二也被五挡住了,所以二最近的比他大的数也为五 ans[0,5,5]

再来看一个例子:


2a2d35a3e87e4d2887c87f34d9915ddf.png


依旧先把值的图画出来.


89fb3d48022041318b66cce77a554dda.jpg


我们从后向前遍历这个链表,

五没有任何数挡住他,则放入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(因为是第一个)

之后依次比较

若这个数小于顶部数据,则说明离他最近比他大的就是顶部数据.将其存入栈

若这个数大于顶部数据,则说明顶部数据需要更新了:将顶部数据依次移出,并比较一下其是否还小于这个数.若大于则说明离这个数最近的比他大的数被找到了.

则将顶部数据放入栈.


77425117c3544bafa7e467e57ecb4941.jpg


当然最开始要先将链表逆转一下 否则无法从后向前遍历.


83394d0562c54e86b7710d4a882b7e08.jpg


代码实现:


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. 链表中的下一个更大节点 --单调栈】已经结束。


🌈若对你有些许帮助,可以点赞、关注、评论支持下博主,你的支持将是我前进路上最大的动力。


🌈若以上内容有任何问题,欢迎在评论区指出。若对以上内容有任何不解,都可私信评论询问。


🌈诸君,山顶见!

目录
相关文章
|
2天前
LeetCode链表hard 有思路?但写不出来?
LeetCode链表hard 有思路?但写不出来?
链表遍历,链表查找和统计节点,链表插入新节点,链表删除节点,链表修改指定节点,链表头插法,尾插法总结
链表遍历,链表查找和统计节点,链表插入新节点,链表删除节点,链表修改指定节点,链表头插法,尾插法总结
|
2天前
|
索引
每日一题:力扣328. 奇偶链表
每日一题:力扣328. 奇偶链表
13 4
|
2天前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
6 0
|
2天前
leetcode代码记录(完全二叉树的节点个数
leetcode代码记录(完全二叉树的节点个数
7 1
|
2天前
leetcode代码记录(移除链表元素
leetcode代码记录(移除链表元素
10 0
|
2天前
|
存储 Java
高效删除链表倒数节点最优实现
要删除链表的倒数第 n 个节点,并返回链表的头节点,我们可以使用一趟扫描的方法来实现。这个方法涉及使用两个指针:快指针和慢指针。
【每日一题】LeetCode——反转链表
【每日一题】LeetCode——反转链表
【每日一题】LeetCode——链表的中间结点
【每日一题】LeetCode——链表的中间结点
|
2天前
|
存储
线性表、链表、栈和队列的初始化
线性表、链表、栈和队列的初始化
17 1

热门文章

最新文章