golang刷leetcode 技巧（62）全 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 <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<n.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();
 */