创建时间： 2019/8/12 15:25
作者： sunpengwei1992@aliyun.com

问题

给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node1, 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

示例

输入：[2,1,5] 输出：[5,5,0] 输入：[2,7,4,3,5] 输出：[7,0,5,5,0]

在看解法之前，请大家先思考下，自己该怎么解决呢

解法一

  • 笨办法，将链表转换为数组，双重for循环，依次找到每个元素的的下一个更大值，然后存储到数组，最后转化为链表返回。

    解法二

  • 遍历链表，将第一个元素入栈，第二元素和已入栈的元素比较，如果大于则将已入栈的元素弹出，将当前元素放入新链表的尾节点，继续和栈中的元素比较，还是大于的话，则将当前元素再放入新链表的尾节点，直到栈中没有元素或者碰到当前元素小于栈中的元素，则将当前元素放入栈中，继续循环，下面画张图来理解一下，光看文字理解起来比较费劲，如下图

链表-快速寻找链表中的下一个更大节点?你怎么做 - 图1

  • 代码实现：代码是没法运行的，因为GoLang没有内置的栈数据结构

    1. type ListNode struct {
    2.    Val int
    3.    Next *ListNode
    4. }
    5. func nextLargerNodes(head *ListNode) []int {
    6.   result := make([]int,0)
    7.   //创建一个栈（这个栈是虚拟的，GoLang中没有内置的栈数据结构）
    8.   s := new(Stack)
    9.   //将首节点值放入
    10.   s.Push(head.Val)
    11.   temp = head.Next
    12.   index := 0
    13.   //从第二节点遍历链表
    14.   for temp != nil{
    15.      index ++
    16.      for s.IsNotEmpty(){
    17.           v := s.Pop()
    18.           //如果小于栈中的值就放入栈中
    19.           if temp.Val < v{
    20.               s.Push(temp.Val)
    21.               result = append(result,0)
    22.               break
    23.           }else{
    24.               //否则，将当前元素放入返回的结果中
    25.               index -- 
    26.               result[index] = temp.Val
    27.           }
    28.      }
    29.      temp = temp.Next
    30.   }
    31.   //针对链表的最后一个元素补0
    32.   result = append(result,0)
    33.   return result
    34. }

    解法三

  • 先声明两个切片status（存储链表的值),result(存储下一个节点比当前节点大的值）,for循环链表，将链表的节点的值放入status中，同时比较下一个节点的值是否比当前节点的值，如果大于，将下一个节点的值添加result中，否则给result加0，最后循环result节点，发现不为0的值时往前倒退，看看status中是否有比它更小的值，如果有则将这个不为0的值放入result这个下标处。

    1. func nextLargerNodes(head *ListNode) []int {
    2.   if head == nil{
    3.       return nil
    4.   } 
    5.   status := make([]int,0)
    6.   result := make([]int,0)
    7.   for head.Next != nil{
    8.       status = append(status,head.Val)     
    9.       if head.Next.Val > head.Val{
    10.           result = append(result,head.Next.Val)
    11.       }else{
    12.           result = append(result,0)
    13.       }
    14.       head = head.Next
    15.   }
    16.   //把末尾数据补进来
    17.   result = append(result,0)
    18.   status = append(status,head.Val)
    19.   //遍历result
    20.   for i,v := range result{
    21.       //下标为0的不参与
    22.       if i==0{
    23.           continue
    24.       }
    25.       //当值不为0时，用当前值和链表之前的数据比较，看看
    26.       //是否有小于当前的值,如果小的话，就把result中为0的替换
    27.       if v !=0{
    28.           for temp := i-1;temp>=0;temp--{
    29.               if v <= status[temp]{
    30.                   continue
    31.               }
    32.               if result[temp] == 0{
    33.                   result[temp] = v
    34.               }
    35.           }
    36.       }
    37.   }
    38.   return result
    39. }

    欢迎大家关注微信公众号：“golang那点事”，更多精彩期待你的到来
    GoLang公众号.jpg