每日一题(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]
    

    提示：

    • 链表中节点数为 n
    • 1 <= n <= 104
    • 1 <= Node.val <= 109

2.解题思路

思路一：使用单调栈

1.我们创建一个单调栈（递减栈），这个栈中存的元素是pair类型的，pair的第一个变量存的是遍历到节点的下标，第二个变量存的是遍历到的节点的值

2.遍历链表，我们每遍历到一个节点，先把当前位置看成是零，放入到一个数组（这里我们用的是动态数组）中，然后看栈中是否有元素

如果栈中有元素，看栈顶元素的值是否小于当前节点的值

如果小于，那么我们通过当前栈顶元素的第二个变量，找到数组应该修改的那个元素的下标，然后那个元素修改为当前节点的值，将当前栈顶元素删除，再重新看栈顶元素与当前元素的关系进行操作，当然如果栈中没有元素了，就不进行操作了。继续接下来的操作

如果大于，就继续接下来的操作（这是一个递减栈，如果栈顶元素都大于当前节点的的值了，那栈中其他元素也一定大于当前节点的值了）

如果栈中没有元素，继续接下来的操作

3.最后将当前节点的下标和当前节点的值作为一个整体放到栈中，继续遍历链表的下一个节点

4.遍历完链表之后，得到的数组就是我们的最终答案

3.写出代码

思路一的代码

class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> ans;
        //pair的第一个变量存的是遍历到节点的下标，第二个变量存的是遍历到的节点的值
        stack<pair<int,int>> sta;
        int index=-1;
        ListNode* cur=head;
        while(cur){
            ans.push_back(0);
            index++;
            while(!sta.empty()&&sta.top().second<cur->val){
                ans[sta.top().first]=cur->val;
                sta.pop();
            }
            sta.push(make_pair(index,cur->val));
            cur=cur->next;
        }
        return ans;
    }
};