外贸seo建站,优化seo教程,兰州企业网站制作,浙江省建设培训中心网站每日一题(LeetCode)----链表–链表中的下一个更大节点
1.题目#xff08;1019. 链表中的下一个更大节点#xff09; 给定一个长度为 n 的链表 head 对于列表中的每个节点#xff0c;查找下一个 更大节点 的值。也就是说#xff0c;对于每个节点#xff0c;找到它旁边的第…每日一题(LeetCode)----链表–链表中的下一个更大节点
1.题目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]提示 链表中节点数为 n1 n 1041 Node.val 109
2.解题思路
思路一使用单调栈
1.我们创建一个单调栈递减栈这个栈中存的元素是pair类型的pair的第一个变量存的是遍历到节点的下标第二个变量存的是遍历到的节点的值
2.遍历链表我们每遍历到一个节点先把当前位置看成是零放入到一个数组这里我们用的是动态数组中然后看栈中是否有元素
如果栈中有元素看栈顶元素的值是否小于当前节点的值
如果小于那么我们通过当前栈顶元素的第二个变量找到数组应该修改的那个元素的下标然后那个元素修改为当前节点的值将当前栈顶元素删除再重新看栈顶元素与当前元素的关系进行操作当然如果栈中没有元素了就不进行操作了。继续接下来的操作
如果大于就继续接下来的操作这是一个递减栈如果栈顶元素都大于当前节点的的值了那栈中其他元素也一定大于当前节点的值了
如果栈中没有元素继续接下来的操作
3.最后将当前节点的下标和当前节点的值作为一个整体放到栈中继续遍历链表的下一个节点
4.遍历完链表之后得到的数组就是我们的最终答案
3.写出代码
思路一的代码
class Solution {
public:vectorint nextLargerNodes(ListNode* head) {vectorint ans;//pair的第一个变量存的是遍历到节点的下标第二个变量存的是遍历到的节点的值stackpairint,int sta;int index-1;ListNode* curhead;while(cur){ans.push_back(0);index;while(!sta.empty()sta.top().secondcur-val){ans[sta.top().first]cur-val;sta.pop();}sta.push(make_pair(index,cur-val));curcur-next;}return ans;}
};
