【leetcode】1019. Next Greater Node In Linked List

末蓝、 2022-01-10 06:11 183阅读 0赞

**题目如下：**

> We are given a linked list with `head` as the first node. Let's number the nodes in the list: `node_1, node_2, node_3, ...` etc.
> 
> 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`.
> 
> Return an array of integers `answer`, where `answer[i] = next_larger(node_{i+1})`.
> 
> Note that in the example inputs (not outputs) below, arrays such as `[2,1,5]` represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.
> 
> Example 1:
> 
>     Input: [2,1,5]
>     Output: [5,5,0]
> 
> Example 2:
> 
>     Input: [2,7,4,3,5]
>     Output: [7,0,5,5,0]
> 
> Example 3:
> 
>     Input: [1,7,5,1,9,2,5,1]
>     Output: [7,9,9,9,0,5,0,0]
> 
> Note:
> 
> 1.  `1 <= node.val <= 10^9` for each node in the linked list.
> 2.  The given list has length in the range `[0, 10000]`.

**解题思路：**本题是找出离自己最近的大于自己的数，和以前做过的 [【leetcode】84. Largest Rectangle in Histogram][leetcode_84. Largest Rectangle in Histogram] 非常相似，区别在于[【leetcode】84. Largest Rectangle in Histogram][leetcode_84. Largest Rectangle in Histogram] 是找出最近的比自己小的数，但是原理是一样的。我的解法就是把链表转成list，然后参照[【leetcode】84. Largest Rectangle in Histogram][leetcode_84. Largest Rectangle in Histogram]的解法。

**代码如下：**

# Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def nextLargerNodes(self, head):
            """
            :type head: ListNode
            :rtype: List[int]
            """
            val = []
            while head != None:
                val.append(head.val)
                head = head.next
            res = [0] * len(val)
            for i in range(len(val)-2,-1,-1):
                next = i+1
                while res[next] != 0 and val[i] >= val[next] :
                    next = res[next]
                if val[i] >= val[next]:
                    res[i] = 0
                else:
                    res[i] = next
            #print res
            for i in range(len(res)):
                if res[i] == 0:
                    continue
                res[i] = val[res[i]]
            return res

转载于:https://www.cnblogs.com/seyjs/p/10636802.html

[leetcode_84. Largest Rectangle in Histogram]: https://www.cnblogs.com/seyjs/p/9467680.html