黄哥Python:1019题Next Greater Node In Linked List解题思路

黄哥Python:1019题Next Greater Node In Linked List解题思路

LeetCode 1019题Next Greater Node In Linked List解题思路

先读题。

1、题目要求单链表当前元素的下一个比它的值大的结点的值，要求

Each node may have a next larger value: for node_i, next_larger(node_i) is the node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible choice. If such a j does not exist, the next larger value is 0.

2、可以用设置一个函数，从一个结点开始，遍历到比它大的值大的，就返回，再从头遍历链接，调用这个函数。但这个方法时间复杂度为O(n^2)，可能会超时。

3、题目有提示，维护一个从栈低往栈顶递降的栈。

解题思路：

1、先遍历链表，将所有的元素添加到一个数组nums（Python用list，Go 用slice）中。

2、生成一个大小为数组长度、元素为0 的res 数组。

3、从头开始遍历nums。如果栈不为空，并且栈（栈中保存数组nums的索引i）顶的值，nums[栈顶的值]小于当前遍历nums[i] 的值，那么pop().

并将res对应栈pop()出的值为索引赋值为nums[i]

4、添加i 到栈中。

请看黄哥Python 黄哥所写的Python代码和Go 语言代码。

下面是Python 代码

下面是Go 语言代码