1. 題目

給出一個以頭節(jié)點 head 作為第一個節(jié)點的鏈表。鏈表中的節(jié)點分別編號為：node_1, node_2, node_3, … 。

每個節(jié)點都可能有下一個更大值（next larger value）：對于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的選項中最小的那個。

如果不存在這樣的 j，那么下一個更大值為 0 。

返回整數(shù)答案數(shù)組 answer，其中 answer[i] = next_larger(node_{i+1}) 。

注意：在下面的示例中，諸如 [2,1,5] 這樣的輸入（不是輸出）是鏈表的序列化表示，其頭節(jié)點的值為 2，第二個節(jié)點值為 1，第三個節(jié)點值為 5 。

示例 1： 輸入：[2,1,5] 輸出：[5,5,0]示例 2： 輸入：[2,7,4,3,5] 輸出：[7,0,5,5,0]示例 3： 輸入：[1,7,5,1,9,2,5,1] 輸出：[7,9,9,9,0,5,0,0]提示： 對于鏈表中的每個節(jié)點，1 <= node.val <= 10^9 給定列表的長度在 [0, 10000] 范圍內(nèi)

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/next-greater-node-in-linked-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 單調(diào)遞減棧

保持棧內(nèi)元素單調(diào)遞減，一旦不滿足就彈棧，直到滿足單調(diào)遞減

class Solution { public:vector<int> nextLargerNodes(ListNode* head) {vector<int> ans;stack<int> stk;//存儲數(shù)值stack<int> idx;//存儲下標(biāo)int n = 0;for( ; head; head=head->next){while(!stk.empty() && stk.top() < head->val)//不單調(diào)遞減{stk.pop();ans[idx.top()] = head->val;//當(dāng)前位置找到了比它大的最近的數(shù)idx.pop();}stk.push(head->val);//數(shù)值idx.push(n++);//下標(biāo)ans.push_back(0);//比當(dāng)前數(shù)大的還未出現(xiàn)，先補0}return ans;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1019. 链表中的下一个更大节点（单调栈）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。