43.日常算法

1.LCR 142. 训练计划 IV

题目来源

给定两个以 有序链表 形式记录的训练计划 l1、l2，分别记录了两套核心肌群训练项目编号，请合并这两个训练计划，按训练项目编号 升序 记录于链表并返回。
注意：新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

/*** 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:ListNode* trainningPlan(ListNode* l1, ListNode* l2) {ListNode* ret = new ListNode;ListNode* l1cur = l1;ListNode* l2cur = l2;ListNode* retcur = ret;while (l1cur && l2cur){if (l1cur->val > l2cur->val){retcur->next = l2cur;l2cur = l2cur->next;}else{retcur->next = l1cur;l1cur = l1cur->next;}retcur = retcur->next;}if (l1cur) retcur->next = l1cur;if (l2cur) retcur->next = l2cur;return ret->next;}
};

1. 链表中的下一个更大节点

题目来源

对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。

示例 1：
输入：head = [2,1,5]
输出：[5,5,0]

/*** 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) {// 单调栈，找右边第一个比他大的数vector<int> ret;stack<pair<int, int>> st;ListNode* cur = head;int idx = 0;while (cur){ret.push_back(0);while (!st.empty() && cur->val > st.top().first){ret[st.top().second] = cur->val;st.pop();}st.emplace(cur->val, idx);++idx;cur = cur->next;}return ret;}
};