给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为:node1, node2, node_3, ... 。 每个节点都可能有下一个更大值,对于 nodei,其 nextlarger(nodei) 是 nodej.val,那么就有 j > i,且nodej.val > nodei.val,而 j 是可能的选项中最小的那个,如果不存在这样的 j,那么下一个更大值为 0 。 返回整数答案数组 answer,其中 answer[i] = nextlarger(node{i+1}) 。 注意:在下面的示例中,诸如 [2,1,5] 这样的输入(不是输出)是链表的序列化表示,其头节点的值为 2,第二个节点值为 1,第三个节点值为 5
输入:[2,1,5] 输出:[5,5,0] 输入:[2,7,4,3,5] 输出:[7,0,5,5,0]
在看解法之前,请大家先思考下,自己该怎么解决呢
type ListNode struct {
Val int
Next *ListNode
}
func nextLargerNodes(head *ListNode) []int {
result := make([]int,0)
//创建一个栈(这个栈是虚拟的,GoLang中没有内置的栈数据结构)
s := new(Stack)
//将首节点值放入
s.Push(head.Val)
temp = head.Next
index := 0
//从第二节点遍历链表
for temp != nil{
index ++
for s.IsNotEmpty(){
v := s.Pop()
//如果小于栈中的值就放入栈中
if temp.Val < v{
s.Push(temp.Val)
result = append(result,0)
break
}else{
//否则,将当前元素放入返回的结果中
index --
result[index] = temp.Val
}
}
temp = temp.Next
}
//针对链表的最后一个元素补0
result = append(result,0)
return result
}
func nextLargerNodes(head *ListNode) []int {
if head == nil{
return nil
}
status := make([]int,0)
result := make([]int,0)
for head.Next != nil{
status = append(status,head.Val)
if head.Next.Val > head.Val{
result = append(result,head.Next.Val)
}else{
result = append(result,0)
}
head = head.Next
}
//把末尾数据补进来
result = append(result,0)
status = append(status,head.Val)
//遍历result
for i,v := range result{
//下标为0的不参与
if i==0{
continue
}
//当值不为0时,用当前值和链表之前的数据比较,看看
//是否有小于当前的值,如果小的话,就把result中为0的替换
if v !=0{
for temp := i-1;temp>=0;temp--{
if v <= status[temp]{
continue
}
if result[temp] == 0{
result[temp] = v
}
}
}
}
return result
}
欢迎大家关注微信公众号:“golang那点事”,更多精彩期待你的到来