golang刷leetcode技巧之如何实现全 O(1) 的数据结构

type Node struct{    next *Node    prev *Node    val int      key string}type AllOne struct {    head *Node    tail *Node    m map[string]*Node
}

/** Initialize your data structure here. */func Constructor() AllOne {    ao:=AllOne{        head:&Node{},        tail:&Node{},        m:make(map[string]*Node),    }    ao.head.next=ao.tail    ao.tail.prev=ao.head    return ao}

/** Inserts a new key  with value 1. Or increments an existing key by 1. */func (this *AllOne) Inc(key string)  {    if n,ok:=this.m[key];ok{        this.m[key].val++        next:=n.next        if next==this.tail || next.val>=n.val{            return        }else{             next.prev=n.prev             n.prev.next=next                        for next.next!=this.tail && next.next.val                next=next.next            }                                   n.next=next.next            n.prev=next                        next.next.prev=n            next.next=n        }    }else{        n:=&Node{            val:1,            key:key,            prev:this.head,            next:this.head.next,        }        this.head.next.prev=n        this.head.next=n                this.m[key]=n    }    this.Print()}
func(this*AllOne)Print(){    for n:=this.head.next ;n!=this.tail;n=n.next{        println(n.val)    }}
/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */func (this *AllOne) Dec(key string)  {    if _,ok:=this.m[key];!ok {        return    }        n:= this.m[key]    if this.m[key].val>1{       n.val--        if n.prev==this.head || n.prev.val<=n.val{            return        }else {            prev:=n.prev             prev.next=n.next             n.next.prev=prev                        for prev.prev!=this.head && prev.prev.val>n.val{                prev=prev.prev            }                        n.prev=prev.prev            n.next=prev                        prev.prev.next=n            prev.prev=n        }    }else{        n.prev.next=n.next        n.next.prev=n.prev        delete(this.m,key)           }   this.Print()   }

/** Returns one of the keys with maximal value. */func (this *AllOne) GetMaxKey() string {     if this.head.next==this.tail{        return ""    }    return this.tail.prev.key}

/** Returns one of the keys with Minimal value. */func (this *AllOne) GetMinKey() string {    if this.head.next==this.tail{        return ""    }    return this.head.next.key}

/** * Your AllOne object will be instantiated and called as such: * obj := Constructor(); * obj.Inc(key); * obj.Dec(key); * param_3 := obj.GetMaxKey(); * param_4 := obj.GetMinKey(); */