题目 #

You are given the head of a linked list.

Remove every node which has a node with a strictly greater value anywhere to the right side of it.

Return the head of the modified linked list.

Example 1:

Input: head = [5,2,13,3,8]
Output: [13,8]
Explanation: The nodes that should be removed are 5, 2 and 3.
- Node 13 is to the right of node 5.
- Node 13 is to the right of node 2.
- Node 8 is to the right of node 3.

Example 2:

Input: head = [1,1,1,1]
Output: [1,1,1,1]
Explanation: Every node has value 1, so no nodes are removed.

Constraints:

The number of the nodes in the given list is in the range $[1, 10^5]$.
$1 <= Node.val <= 10^5$

思路1 反向最大值遍历 #

分析 #

自己想的
将链表所有的val存到数组中，然后处理数据，让 $arr[i] = \max \limits_{i \le x < n}$ arr
遍历链表，如果当前小于 $arr[i]$ ，就跳过，相等就赋值

代码 #

 1func removeNodes(head *ListNode) *ListNode {
 2	cur := head
 3	arr := make([]int, 0, 1)
 4	for cur != nil {
 5		arr = append(arr, cur.Val)
 6		cur = cur.Next
 7	}
 8	max := arr[len(arr)-1]
 9	for i := len(arr) - 2; i >= 0; i-- {
10		if max < arr[i] {
11			max = arr[i]
12		} else {
13			arr[i] = max
14		}
15	}
16
17	cur = head
18	resultTmp := &ListNode{
19		Next: head,
20	}
21	last := resultTmp
22	for i := 0; i < len(arr); i++ {
23		if cur.Val < arr[i] {
24			last.Next = cur.Next
25		} else {
26			last = cur
27		}
28		cur = cur.Next
29	}
30	return resultTmp.Next
31}

思路2 链表转数组处理 #

分析 #

将链表所有节点放到数组中
每放一个节点，查看前面的节点是否比它小，如果比它小就替代

代码 #

 1func removeNodes1(head *ListNode) *ListNode {
 2	arr := make([]*ListNode, 0, 1)
 3	for p := head; p != nil; p = p.Next {
 4		t := len(arr) - 1
 5		for t >= 0 && arr[t].Val < p.Val {
 6			arr = arr[:t]
 7			t--
 8		}
 9		arr = append(arr, p)
10	}
11	for i := 0; i < len(arr)-1; i++ {
12		arr[i].Next = arr[i+1]
13	}
14	return arr[0]
15}