# LeetCode - 1019. Next Greater Node In Linked List
### 題目網址：https://leetcode.com/problems/next-greater-node-in-linked-list/
###### tags: `LeetCode` `Medium` `堆疊（Stack）` `連結串列（Linked List）`

/*
    -LeetCode format-
    Problem: 1019. Next Greater Node In Linked List
    Difficulty: Medium
    
    by Inversionpeter
*/



static const auto Initialize = []{
    ios::sync_with_stdio(false); cout.tie(nullptr);
    return nullptr;
}();

/**
 * 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> answer;
        answer.reserve(10000);
        stack <pair<int, int>> decreasing;
        int nowIndex = 0;
        while (head) {
            while (!decreasing.empty() && head->val > decreasing.top().first) {
                answer[decreasing.top().second] = head->val;
                decreasing.pop();
            }
            decreasing.emplace(head->val, nowIndex);
            answer.push_back(0);
            head = head->next;
            ++nowIndex;
        }
        return answer;
    }
};