如何找出单向链表中每个节点之后的下个较大值?
如何找出单向链表中每个节点之后的下个较大值,如果不存在则返回0?
例如:
链表list:[6,4,5,2,8,2,5,1]
元素对应较大值result:[8,5,8,8,0,5,0,0]
首先我们分析下:
1. 要找到的是一个元素之后下个较大值,这里的关键词是[下个较大值]是其后第一个大于当前元素的值.如例子中,第二个元素4(list[1])对应的下个较大值应为5,而不是8.
2. 元素8,在其之后没有比8大的值,所以对应的较大值为0;
3. 最后一位元素1,后面没有元素,所以是0;
4. 要找到一个元素其后的较大值,就需要对该元素之后的元素进行遍历,并找到这个较大值,这样的遍历方式的时间复杂度是O(n^2),并且很多元素会被多次遍历到,肯定不是一个高效的遍历方式.
5. 那如果能反向遍历呢?通过对遍历过的数据进行记录,能更容易的找到任何一个元素对应的较大值.
6. 那什么样的数据结构适合这种记录呢?带着这两个问题,我们先看下反向遍历链表时,需要记录哪些元素值:
分析下反向遍历过程
1. 第2次遍历时,发现较大值5是在后续遍历中可能再次用到的,记录下来.
2. 第4次遍历时,发现较大值8是在后续遍历中可能再次用到的,已经记录的较大值5已经不会再用了,需删除掉.较大值需记录值只有8.
3. 第6次遍历时,元素5的较大值仍为8;但自身也需要记录下,例如前边元素值为4时,较大值则为5.此时需要记录的较大值为5,8.
4. 第7次遍历时,元素4的较大值为5,存在于较大值列表内,而且本身同样需要记录到较大值列表中.
5. 第8次遍历时,元素较大值是8;需要记录到较大值列表中;同时,已经记录的较大值列表中4和5也不会被再次使用,删除掉.
可以发现,在反向遍历时,
1.当前元素比已经记录的元素的小时,则把当前元素直接添加到记录中;
2.当前元素比已经记录元素大时,则将记录中小于该元素值的记录全部删除,并把当前元素添加到记录中;可以参考第4次遍历和第8次遍历.
上述两个过程可以对应到数据结构中的栈操作,且存入栈中的元素始终是有序的(递增),所以可以选用单调栈作为存储模型更为适合.具体实现参考代码.
单调栈
单调栈就是栈内元素单调递增或者单调递减的栈.
单调递增栈的基本操作是栈为空或入栈元素值小于栈顶元素值，则入栈；否则，如果入栈则会破坏栈的单调性，则需要把比入栈元素小的元素全部出栈。单调递减的栈反之。
一般适合解决视野总和,柱状图的最大矩形,求最大区间等等相关问题.
恭喜你又学会了一种算法!
附上代码:
public class NextLargerNodes {
static int[] nextLargerNodes(ListNode head) {
ArrayList<Integer> list = new ArrayList<>();
while (head != null) {
list.add(head.val);
head = head.next;
}
int size = list.size();
Stack<Integer> stack = new Stack<>();
int[] result = new int[size];
for (int i = list.size() - 1; i >= 0; i--) {
while (!stack.empty() && stack.peek() <= list.get(i)) {
stack.pop();
}
result[i] = stack.empty() ? 0 : stack.peek();
stack.push(list.get(i));
}
return result;
}
public static void main(String[] args) {
//[6,4,5,2,8,2,5,1]
//[8,5,8,8,0,5,0,0]
ListNode node = new ListNode(6).nextNode(new ListNode(4).nextNode(
new ListNode(5).nextNode(new ListNode(2).nextNode(new ListNode(8)
.nextNode(new ListNode(2).nextNode(new ListNode(5).nextNode(new ListNode(1))))))));
Assert.assertArrayEquals(new int[]{8,5,8,8,0,5,0,0}, nextLargerNodes(node));
}
static class ListNode {
int val;
ListNode next;
public ListNode(int data) {
this.val = data;
}
public ListNode nextNode(ListNode node) {
this.next = node;
return this;
}
public String toString() {
return "Node{" +
"data=" + val +
", next=" + next +
'}';
}
}
}
腾讯云开发者
