当前位置 博文首页 > shijiujiu33的博客:LeetCode链表算法——1019. 链表中的下一个
题目描述:
题目链接:链表中的下一个更大节点
读懂题目大致意思就是:求出链表每个结点的“最大值”,该“最大值”指的是,其后第一个结点值比他大的结点的值
首先我想到的就是:两次循环,遍历每个结点,每个结点再往后遍历,找出其后第一个最大的结点的值即可
详细代码:
public int[] nextLargerNodes(ListNode head) {
if (head == null) {
return new int[0];
}
ListNode frist = head;
ListNode front = head;
// 先获取链表的长度
int length = 1;
while (head.next != null) {
length++;
head = head.next;
}
int[] ints = new int[length];
// 两次循环,时间复杂度(n*n)过高,超过时间限制,不推荐
for (int i = 0; i < length - 1; i++) {
for (int j = i; j < length - 1; j++) {
if (front.next != null && front.next.val > frist.val) {
ints[i] = front.next.val;
break;
}
front = front.next;
}
frist = frist.next;
front = frist;
}
return ints;
}
感觉很简单,但是很遗憾,提交的时候,LeetCode显示超出时间限制,不予通过
后面看了一些推荐算法,推荐使用栈来辅助完成
这里记录一下就是为什么会想到用栈呢?
栈数据结构简单,先进先出
从前往后遍历入栈,当遇到待入栈元素比栈顶元素大的时候,栈顶元素出栈
这是不是就对应着:找出某结点其后第一个最大的结点的值
每一次出栈即意味着找到了他的“最大值”(其后第一个比他大的)
但还有一点需要注意的是,需要记录出栈元素在原链表中的位置索引,因为需要输出对应的“最大值”数组
所以引入了Java类库中的Pair
,配对类,有一个key和一个value组成
即在元素入栈的时候,就记录好该元素在原链表中的位置,这样出栈的时候,就很方便往目标数组中赋值
代码如下:
// 使用中间数据结构——栈 辅助解决,时间复杂度低
public int[] nextLargerNodesByStack(ListNode head) {
if (head == null) {
return new int[0];
}
// 使用集合接受,可以避免一个遍历(查找长度)
List<Integer> list = new ArrayList<>();
int count = 0;
// 引入了Pair配对类,一个key,一个value,因为这里需要记录原链表每个结点的索引和value
Stack<Pair<Integer, Integer>> stack = new Stack<>();
while (head != null) {
// 初始每个添加0,后出栈则相应更新
list.add(0);
while (!stack.empty() && head.val > stack.peek().getValue()) {
// 栈不为空且待入栈元素大于栈顶元素,则栈顶元素出栈
Pair<Integer, Integer> pop = stack.pop();
list.set(pop.getKey(), head.val);
}
stack.push(new Pair<>(count, head.val));
head = head.next;
count++;
}
// List<Integer> 转 int[]
return list.stream().mapToInt(Integer::intValue).toArray();
}
LeetCode提交,通过
下次类似”排序“算法,可以优先考虑是否可以使用栈辅助完成
记录一下:说明自己的算法道路还很长,继续加油
cs