C语言重构【1019】链表中的下一个更大节点

た入场券 2022-11-07 04:16 64阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。
    
    每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且  node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。
    
    返回整数答案数组 answer，其中 answer[i] = next_larger(node_{ i+1}) 。
    
    注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。
    
     
    
    示例 1：
    
    输入：[2,1,5]
    输出：[5,5,0]
    示例 2：
    
    输入：[2,7,4,3,5]
    输出：[7,0,5,5,0]
    示例 3：
    
    输入：[1,7,5,1,9,2,5,1]
    输出：[7,9,9,9,0,5,0,0]
     
    
    提示：
    
    对于链表中的每个节点，1 <= node.val <= 10^9
    给定列表的长度在 [0, 10000] 范围内

#### 方案： ####

*  单调栈的应用：[个人理解][Link 1]

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution
    { 
    public:
        vector<int> nextLargerNodes(ListNode *head)
        { 
    
            stack<int> s;
            stack<int> index;
            int count = 0;
            ListNode *tmp = head;
            while (tmp != NULL)
            { 
                tmp = tmp->next;
                count++;
            }
            vector<int> res(count, 0);
            tmp = head;
            count = 0;
            while (tmp != NULL)
            { 
                while ((!s.empty()) && s.top() < tmp->val)
                { 
                    res[index.top()] = tmp->val;
                    s.pop();
                    index.pop();
                }
                s.push(tmp->val);
                index.push(count);
                count++;
                tmp = tmp->next;
            }
            return res;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode
[Link 1]: https://blog.csdn.net/symuamua/article/details/114649796