全 O(1) 的数据结构

题目描述：

请你实现一个数据结构支持以下操作：

Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否则使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串”” 。
GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串””。

挑战：

你能够以 O(1) 的时间复杂度实现所有操作吗？

思路:

跟LRU类似，用哈希双向链表来做，还有很多不足，代码有些插入和删除可以提取出来写成函数，懒了。

代码:

type AllOne struct {
	mp   map[string]*node
	tail *node
	head *node
}
type node struct {
	next  *node
	pre   *node
	key   string
	value int
}

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

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
func (this *AllOne) Inc(key string) {

	if _, ok := this.mp[key]; ok {
		this.mp[key].value++
		nodeNext := this.mp[key].next
		//delete the node
		this.mp[key].pre.next = this.mp[key].next
		this.mp[key].next.pre = this.mp[key].pre

		for this.mp[key].value >= nodeNext.value && nodeNext != this.tail {
			nodeNext = nodeNext.next
		}
		nodeNext.pre.next = this.mp[key]
		this.mp[key].pre = nodeNext.pre
		this.mp[key].next = nodeNext
		nodeNext.pre = this.mp[key]
	} else {
		//insert
		headNext := this.head.next
		node := &node{key: key, value: 1}
		this.mp[key] = node
		this.head.next = this.mp[key]
		this.mp[key].pre = this.head
		this.mp[key].next = headNext
		headNext.pre = this.mp[key]
	}
}

/* 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 this.mp[key].value > 1 {
		this.mp[key].value--
	} else {
		this.mp[key].pre.next = this.mp[key].next
		this.mp[key].next.pre = this.mp[key].pre
		delete(this.mp, key)
	}
}

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

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

代码效率：

执行用时：36 ms, 在所有 Go 提交中击败了84.78%的用户
内存消耗：9.3 MB, 在所有 Go 提交中击败了99.46%的用户