专栏首页GoLang那点事链表-快速寻找链表中的下一个更大节点?你怎么做

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

问题

给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为:node1, node2, node_3, ... 。 每个节点都可能有下一个更大值,对于 nodei,其 nextlarger(nodei) 是 nodej.val,那么就有 j > i,且nodej.val > nodei.val,而 j 是可能的选项中最小的那个,如果不存在这样的 j,那么下一个更大值为 0 。 返回整数答案数组 answer,其中 answer[i] = nextlarger(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循环,依次找到每个元素的的下一个更大值,然后存储到数组,最后转化为链表返回。

解法二

  • 遍历链表,将第一个元素入栈,第二元素和已入栈的元素比较,如果大于则将已入栈的元素弹出,将当前元素放入新链表的尾节点,继续和栈中的元素比较,还是大于的话,则将当前元素再放入新链表的尾节点,直到栈中没有元素或者碰到当前元素小于栈中的元素,则将当前元素放入栈中,继续循环,下面画张图来理解一下,光看文字理解起来比较费劲,如下图
  • 代码实现:代码是没法运行的,因为GoLang没有内置的栈数据结构
type ListNode struct {
     Val int
     Next *ListNode
}
func nextLargerNodes(head *ListNode) []int {
    result := make([]int,0)
    //创建一个栈(这个栈是虚拟的,GoLang中没有内置的栈数据结构)
    s := new(Stack)
    //将首节点值放入
    s.Push(head.Val)
    temp = head.Next
    index := 0
    //从第二节点遍历链表
    for temp != nil{
       index ++
       for s.IsNotEmpty(){
            v := s.Pop()
            //如果小于栈中的值就放入栈中
            if temp.Val < v{
                s.Push(temp.Val)
                result = append(result,0)
                break
            }else{
                //否则,将当前元素放入返回的结果中
                index -- 
                result[index] = temp.Val
            }
       }
       temp = temp.Next
    }
    //针对链表的最后一个元素补0
    result = append(result,0)
    return result
}

解法三

  • 先声明两个切片status(存储链表的值),result(存储下一个节点比当前节点大的值),for循环链表,将链表的节点的值放入status中,同时比较下一个节点的值是否比当前节点的值,如果大于,将下一个节点的值添加result中,否则给result加0,最后循环result节点,发现不为0的值时往前倒退,看看status中是否有比它更小的值,如果有则将这个不为0的值放入result这个下标处。
func nextLargerNodes(head *ListNode) []int {
    if head == nil{
        return nil
    } 
    status := make([]int,0)
    result := make([]int,0)
    for head.Next != nil{
        status = append(status,head.Val)     
        if head.Next.Val > head.Val{
            result = append(result,head.Next.Val)
        }else{
            result = append(result,0)
        }
        head = head.Next
    }
    //把末尾数据补进来
    result = append(result,0)
    status = append(status,head.Val)
    //遍历result
    for i,v := range result{
        //下标为0的不参与
        if i==0{
            continue
        }
        //当值不为0时,用当前值和链表之前的数据比较,看看
        //是否有小于当前的值,如果小的话,就把result中为0的替换
        if v !=0{
            for temp := i-1;temp>=0;temp--{
                if v <= status[temp]{
                    continue
                }
                if result[temp] == 0{
                    result[temp] = v
                }
            }
        }
    }
    return result
}

欢迎大家关注微信公众号:“golang那点事”,更多精彩期待你的到来

本文分享自微信公众号 - GoLang那点事(aweiaichitudou),作者:那小子阿伟

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 链表-删除排序链表中的重复元素,你能想到几种解法?

    阿伟
  • 链表-两数相加

    给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储一位数字。如果,我们将这两个数相加起来,则会...

    阿伟
  • 链表-如何高效删除链表的倒数第N个节点

    好了,删除链表倒数第N个节点就分享到这里,有收获的帮忙关注,转发,点赞呗,非常感谢。

    阿伟
  • (10) 如何MySQL读压力大的问题

    读写分离时,需要注意,对于实时性要求比较高的数据,不适合在从库上查询(因为主从复制存在一定延迟(毫秒级)),比如库存就应该在主库上查询,如果放在从库上查询,可能...

    用户1214487
  • Python 面向对象封装 - 肥仔类

    Devops海洋的渔夫
  • Istio各模块组件的通信方式梳理

    从istio的架构中,可以看到,整体组件包括Pilot、Mixer、Citadel、Proxy;其中Proxy 默认采⽤用Envoy,是可以替代为其他组件的。

    Allen.Wu
  • 产品资讯|腾讯优图小程序上线,带你探索更多玩法

    我们先选择车辆属性识别来体验下,目前优图车辆属性识别支持9种车身颜色、18种车型、200多种品牌、4000多种车系的识别,拍照上传后就知道是什么车。在实际应用中...

    优图实验室
  • WebForms和MVC这2个模型都很棒,由相关讨论想到的

    看了为WebForms说几句话,以及一些ASP.NET开发上的经验(上) 和为 MVC 和 Web Form 正名的一份“大字报” 的相关评论。 ...

    张善友
  • [CVPR 2019] Pose2Seg:检测免费的人体实例分割

    在这篇文章中,将从CVPR 2019回顾论文“Pose2Seg:Detection Free Human Instance Segmentation”。本文提出...

    代码医生工作室
  • 美NSF支持脑电波生物识别研究

    美国自然科学基金会(NSF)向纽约宾汉姆顿大学拨款90万美元,用于支持脑电波生物识别技术研究。 据该校研究负责人Zhanpeng Jin描述,这一名为“大脑破解...

    人工智能快报

扫码关注云+社区

领取腾讯云代金券