[数据结构与算法] 算法--链表中的下一个更大节点(Kotlin)

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 算法--链表中的下一个更大节点(Kotlin) -> 正文阅读

[数据结构与算法]算法--链表中的下一个更大节点(Kotlin)

给定一个长度为 n 的链表 head

对于列表中的每个节点，查找下一个更大节点的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值严格大于它的值。

返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。

示例 1：

在这里插入图片描述

输入：head = [2,1,5]
输出：[5,5,0]
示例 2：
在这里插入图片描述

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

提示：

链表中节点数为 n
1 <= n <= 104
1 <= Node.val <= 109

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-greater-node-in-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决思路：

下一个更大的，这种使用单调栈比较好解决
我想着用map 发现链表中有重复元素
太复杂了还是用单调栈比较简单

参考：
https://leetcode-cn.com/problems/next-greater-node-in-linked-list/solution/5chong-jie-jue-fang-shi-tu-wen-xiang-jie-by-sdwwld/

解决方法：

    fun nextLargerNodes(head: ListNode?): IntArray {
        //使用单调栈
        val result = mutableListOf<Int>()
        var stack = LinkedList<Int>()
        var cur = head
        var i = 0
        while (cur != null){
            while (!stack.isEmpty() && cur.`val` > result[stack.peek()]) {
                result[stack.pop()] = cur.`val`
            }
            stack.push(i++)
            result.add(cur.`val`)
            cur = cur.next
        }
        while (!stack.isEmpty()) {
            result[stack.pop()] = 0
        }
        return result.toIntArray()
    }