题目链接:1019. 链表中的下一个更大节点
方法:单调栈
解题思路
该类问题详解:单调栈解决 Next Greater Number 一类问题
代码
class Solution {
public:
vector<int> nextLargerNodes(ListNode* head) {
vector<int> value;
while (head != nullptr) {
value.push_back(head->val);
head = head->next;
}
int n = value.size();
vector<int> ans(n);
stack<int> stk;
stk.push(value.back());
for (int i = n - 1; i >= 0; i -- ) {
while (!stk.empty() && value[i] >= stk.top()) stk.pop();
ans[i] = stk.empty() ? 0 : stk.top();
stk.push(value[i]);
}
return ans;
}
};
复杂度分析
时间复杂度:O(n);
空间复杂度:O(n)。