?

Halo，這里是Ppeua。平時主要更新C語言，C++，數(shù)據(jù)結構算法......感興趣就關注我吧！你定不會失望。

??個人主頁：主頁鏈接

??算法專欄：專欄鏈接

?????我會一直往里填充內容噠！

??LeetCode專欄：專欄鏈接?

????目前在刷初級算法的LeetBook 。若每日一題當中有力所能及的題目，也會當天做完發(fā)出

??代碼倉庫：Gitee鏈接

??點擊關注=收獲更多優(yōu)質內容??

?

目錄

題目:1019.?鏈表中的下一個更大節(jié)點

?編輯題解:

代碼實現(xiàn):

完結撒花：

題目:1019.?鏈表中的下一個更大節(jié)點

題解:

簡單來說,就是找這個節(jié)點前面離他最近的,且比他大的值.

我們可以把這個鏈表畫成這樣.

那么從右向左遍歷,尋找離他最近的比他大的那個數(shù)是否就可以看成:找把他擋住的那個數(shù).

我們從后向前遍歷這個鏈表,

然后五沒有任何數(shù)擋住他,則放入0? ? ans:[0]

一被五擋住了,所以一最近的比他大的數(shù)為五? ?ans:[0,5]

二也被五擋住了,所以二最近的比他大的數(shù)也為五 ans[0,5,5]

再來看一個例子:

依舊先把值的圖畫出來.

我們從后向前遍歷這個鏈表,

五沒有任何數(shù)擋住他,則放入0? ? ans:[0]

三被五擋住了,所以三最近的比他大的數(shù)為五? ?ans:[0,5]

四也被五擋住了,所以四最近的比他大的數(shù)也為五 ans:[0,5,5]

七沒有任何數(shù)擋住他,則放入0? ans:[0,5,5,0]

二被七擋住了,所以離二最近比其大的數(shù)字為七 ans:[0,5,5,0,7]

因為我們是反向遍歷的,所以最后要將ans 翻轉一下就是答案ans:[7,0,5,5,0]

總結下我們這個過程,就是一個單調棧

我們將最后一個元素放入數(shù)據(jù)頂部,然后在答案數(shù)組中存入0(因為是第一個)

之后依次比較

若這個數(shù)小于頂部數(shù)據(jù),則說明離他最近比他大的就是頂部數(shù)據(jù).將其存入棧

若這個數(shù)大于頂部數(shù)據(jù),則說明頂部數(shù)據(jù)需要更新了:將頂部數(shù)據(jù)依次移出,并比較一下其是否還小于這個數(shù).若大于則說明離這個數(shù)最近的比他大的數(shù)被找到了.

則將頂部數(shù)據(jù)放入棧.

當然最開始要先將鏈表逆轉一下 否則無法從后向前遍歷.

代碼實現(xiàn):

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. 鏈表中的下一個更大節(jié)點 --單調棧】已經(jīng)結束。

??若對你有些許幫助，可以點贊、關注、評論支持下博主，你的支持將是我前進路上最大的動力。

??若以上內容有任何問題，歡迎在評論區(qū)指出。若對以上內容有任何不解，都可私信評論詢問。

??諸君，山頂見！文章來源地址http://www.zghlxwxcb.cn/news/detail-429550.html

到了這里，關于LeetCode每日一題 1019. 鏈表中的下一個更大節(jié)點 --單調棧的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！