golang力扣leetcode 432.全O(1)的数据结构

package main
import "container/list"
type node struct {
  keys  map[string]struct{}
  count int
}
type AllOne struct {
  *list.List
  nodes map[string]*list.Element
}
func Constructor() AllOne {
  return AllOne{
    List:  list.New(),
    nodes: make(map[string]*list.Element),
  }
}
func (l *AllOne) Inc(key string) {
  if cur := l.nodes[key]; cur != nil { //在链表中
    curNode := cur.Value.(node)
    //如果新的key的count不等于下一个的count，则在当前cur后插入一个新的
    if nxt := cur.Next(); nxt == nil || nxt.Value.(node).count > curNode.count+1 {
      l.nodes[key] = l.InsertAfter(node{
        keys:  map[string]struct{}{key: {}},
        count: curNode.count + 1,
      }, cur)
    } else { //下一个节点存在并且count刚好等于新的count
      nxt.Value.(node).keys[key] = struct{}{}
      l.nodes[key] = nxt
    }
    //将key从其所在的节点上删除
    delete(curNode.keys, key)
    if len(curNode.keys) == 0 { //如果没有key就移除这个节点
      l.Remove(cur)
    }
  } else { //不在链表中
    if l.Front() == nil || l.Front().Value.(node).count > 1 { //如果没有头节点，或者头节点的count大于0，则直接插入一个新的
      l.nodes[key] = l.PushFront(
        node{
          map[string]struct{}{key: {}},
          1,
        })
    } else { //如果有头节点，并且头节点的count=1，则插入头节点的keys中
      l.Front().Value.(node).keys[key] = struct{}{}
      l.nodes[key] = l.Front()
    }
  }
}
func (l *AllOne) Dec(key string) {
  cur := l.nodes[key]
  curNode := cur.Value.(node)
  if curNode.count > 1 {
    //如果前一个节点不存在，或则前一个节点的count小于新的count，则直接在前一个结点的后面插入一个新的节点
    if pre := cur.Prev(); pre == nil || pre.Value.(node).count < curNode.count-1 {
      l.nodes[key] = l.InsertBefore(node{
        keys:  map[string]struct{}{key: {}},
        count: curNode.count - 1,
      }, cur)
    } else { //前一个节点存在并且前一个节点的count等于新count
      pre.Value.(node).keys[key] = struct{}{}
      l.nodes[key] = pre
    }
  } else { //说明key只出现过一次，直接移除即可
    delete(l.nodes, key)
  }
  //将key从其所在的节点上删除
  delete(curNode.keys, key)
  //如果这个节点上一个key都没有，则将节点删除
  if len(curNode.keys) == 0 {
    l.Remove(cur)
  }
}
func (l *AllOne) GetMaxKey() string {
  if b := l.Back(); b != nil {
    for key := range b.Value.(node).keys {
      return key
    }
  }
  return ""
}
func (l *AllOne) GetMinKey() string {
  if f := l.Front(); f != nil {
    for key := range f.Value.(node).keys {
      return key
    }
  }
  return ""
}
/**
 * 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();
 */