1019. 链表中的下一个更大节点
题目:
给定一个长度为 n 的链表 head
对于列表中的每个节点,查找下一个 更大节点 的值。也就是说,对于每个节点,找到它旁边的第一个节点的值,这个节点的值 严格大于 它的值。
返回一个整数数组 answer ,其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点,设置 answer[i] = 0 。
示例 1:
输入:head = [2,1,5]
输出:[5,5,0]
示例 2:
输入:head = [2,7,4,3,5]
输出:[7,0,5,5,0]
提示:
链表中节点数为 n
1 <= n <= 104
1 <= Node.val <= 109
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/next-greater-node-in-linked-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路:
首先,我们要先确定链表长度,并且定义两个vector容器和一个栈,用来存储数据和最终结果。(这里主要看函数的类型,是一个vector类型的函数,所以最终返回值也一定是这个)
其次,我们用一个vector容器存储链表中所有数据的值,用另一个vector容器来保存最终结果,栈用来存储下标。我们进行循环,将每一个值的下标逐步放入到栈中,并且每一次循环都要判断当前值是否大于栈头为下标的值,如果大于就将现在循环的值保存到结果vector容器中,下标就是当前栈头的下标,并且将栈头拿出来。文章来源:https://www.toymoban.com/news/detail-416300.html
最后,根据上述操作,我们返回最终结果的vector容器即可。文章来源地址https://www.toymoban.com/news/detail-416300.html
代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
vector<int> nextLargerNodes(ListNode* head) {
int len = 0;
ListNode* p = head;
while(p)
{
p = p->next;
++len;
}
p = head;
vector<int> nodeval(len,0);
stack<int> index;
vector<int> ans(len,0);
for(int i = 0;i < len;i++)
{
nodeval[i] = p->val;
p = p->next;
}
for(int i = 0;i < len;i++)
{
while(!index.empty() && nodeval[i] > nodeval[index.top()])
{
ans[index.top()] = nodeval[i];
index.pop();
}
index.push(i);
}
return ans;
}
};
到了这里,关于入门力扣自学笔记256 C++ (题目编号:1019)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!