题目简介：
给定一个长度为 n 的链表 head
对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。
返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。
示例 1：
1
2
| 输入：head = [2,1,5]
输出：[5,5,0]
|
提示：
- 链表中节点数为
n
1 <= n <= 10^41 <= Node.val <= 10^9
思路：
利用单调栈的性质，若当前元素比栈顶元素小或相等，则直接入栈；否则，一直出栈，当前元素便是所有出栈元素的下一个更大结点。
tip:
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
class Solution {
public:
vector<int> nextLargerNodes(ListNode* head) {
vector<int> res;
stack<pair<int, int>> stk;
int idx = 0;
stk.push(make_pair(idx, head -> val));
head = head -> next;
idx++;
res.push_back(0);
while(head){
if(head -> val <= stk.top().second)
stk.push(make_pair(idx, head -> val));
else{
while(!stk.empty() && stk.top().second < head -> val){
auto item = stk.top();
res[item.first] = head -> val;
stk.pop();
}
stk.push(make_pair(idx, head -> val));
}
res.push_back(0);
head = head -> next;
idx++;
}
return res;
}
};
|
