Java 中链表中的下一个较大节点

给定一个整数链表 L，任务是返回一个整数链表，其中包含给定链表中每个元素的下一个更大元素。如果没有任何元素有更大的元素，则为其输入 0。

示例 1

输入

head = [1, 3, 2, 4]

输出

链表中的下一个更大元素是 [3, 4, 4, 0]

解释

• 3 是 1 后面的第一个更大的元素，是 1 的下一个更大元素。
• 4 是 3 后面的第一个更大的元素，是 3 的下一个更大元素。
• 4 是 2 后面的第一个更大的元素，是 2 的下一个更大元素。
• 由于 4 后面没有更大的元素了，4 的下一个更大元素是 0。

示例 2

输入

head = [2, 1, 5]

输出

链表中的下一个更大元素是 [0, 2, 0]

解释

• 2 的下一个更大元素是 0，因为它后面没有更大的元素了。
• 2 是 1 后面的第一个更大的元素，是 1 的下一个更大元素。
• 5 的下一个更大元素是 0，因为它后面没有更大的元素了。

方法：使用暴力算法

该代码使用分层遍历链表，采用暴力方法，最坏情况下时间复杂度为 O(n²)。结果存储在 O(n) 的空间复杂度中，因为它使用了大小为 n 的数组 (res[])。由于它按顺序测试每个节点与所有后续节点，而不是使用最优的单调栈技术，因此对于大型列表效率不高。在遍历之前，会调用 sizeOfList() 方法，这会增加 O(n) 的开销来确定列表的大小。此外，由于 push() 将元素放在头部，因此列表的构造顺序与插入顺序相反。为确保输出可读，应用程序使用 Arrays.toString() 打印结果。

算法

步骤 1： 从右到左遍历链表，因为我们需要找到下一个更大的元素。

步骤 2： 为了有效地确定每个节点的下一个更大元素，保持栈单调递减。

步骤 3： 只要栈不为空且栈顶元素小于或等于当前正在使用的节点，就从栈中弹出元素。

步骤 4： 如果栈不为空，则栈顶元素是当前节点的下一个更大元素。

步骤 5： 将当前节点压入栈中，以便稍后进行比较。

步骤 6： 维护一个数组以存储后续的较大元素。

步骤 7： 最后，打印最终结果。

实施

输出

 
The next greater element in the Linked List is [7, 4, 7, 0, 0]   

复杂度分析

上述代码的时间复杂度为 O(N²)，其中“N”代表数组中的元素数量，空间复杂度为 O(1)。

方法：使用栈和链表

在单链表中，一个Java程序为每个节点找到下一个更大的元素。为了从右到左处理元素，它首先反转链表。对于每个节点，使用单调递减栈有效地找到下一个更大的元素，确保 O(n) 的时间复杂度。如果找到更大的元素，则将其添加到结果列表中；如果未找到，则分配 0。为了将结果列表恢复到其原始顺序，然后将其反转。使用 push 方法将新节点添加到列表中，并通过 printList 显示输出。整体策略利用栈和链表反转来优化下一个更大元素的搜索。

算法

步骤 1： 反转链表，以便从右到左处理元素。

步骤 2： 初始化一个栈来按递减顺序存储值。

步骤 3： 反向遍历链表。

步骤 3.1： 如果栈为空，则将 0 存储在结果列表中。

步骤 3.2： 如果不为空，则弹出小于或等于显示值的所有元素。

步骤 3.3： 如果栈不为空，则下一个更大的元素位于栈顶；否则，存储 0。

步骤 4： 将该值压入栈中。

步骤 5： 反转结果列表以恢复原始顺序。

实施

输出

 
The next greater element in the Linked List is 
7 4 7 0 0   

复杂度分析

上述代码的时间复杂度为 O(N²)，其中“N”代表数组中的元素数量，空间复杂度为 O(1)。