432. All O`one Data Structure
基本的想法就是利用一个双向链表来维持单调性，每个node的value就是当前key出现的次数，
然后利用keys这个set来维护当前这个value次数下有多少个key。这样取头或者尾就可以得到最大key或者最小key，然后在用一个hash来从key映射到key所在的node，每次增加或者减少value的时候，就移动key所在的node，并且更新映射。
class Node:
def __init__(self, value, next, prev, key):
self.next = next
self.prev = prev
self.value = value
self.keys = {key}
class DoubleList:
def __init__(self):
self.head = Node(-1, None, None, "")
self.tail = Node(-1, None, None, "")
self.head.next = self.tail
self.tail.prev = self.head
def insertAfter(self, n, val, key):
nn = Node(val, n.next, n, key)
n.next = nn
nn.next.prev = nn
return nn
def remove(self, n):
n.prev.next = n.next
n.next.prev = n.prev
del n
class AllOne(object):
def __init__(self):
self.dll = DoubleList()
self.keys = {}
def inc(self, key):
if key not in self.keys:
n = self.dll.insertAfter(self.dll.head, 0, key)
self.keys[key] = n
else:
n = self.keys[key]
if n.value + 1 == n.next.value:
# merge with next
self.keys[key] = n.next
n.keys.remove(key)
n.next.keys.add(key)
elif len(n.keys) == 1:
# increment in place
n.value += 1
else:
# insert new node
nn = self.dll.insertAfter(n, n.value+1, key)
self.keys[key] = nn
n.keys.remove(key)
#Garbage collection
if len(n.keys) <= 0:
self.dll.remove(n)
def dec(self, key):
if key not in self.keys:
return
else:
n = self.keys[key]
if n.value==1:
# remove key/node
del self.keys[key]
n.keys.remove(key)
elif n.value - 1 == n.prev.value:
# merge with previous
self.keys[key] = n.prev
n.keys.remove(key)
n.prev.keys.add(key)
elif len(n.keys) == 1:
# decrement in place
n.value -= 1
else:
# insert new node
nn = self.dll.insertAfter(n.prev, n.value-1, key)
n.keys.remove(key)
self.keys[key] = nn
# Garbage collection
if len(n.keys) <= 0:
self.dll.remove(n)
def getMaxKey(self):
if self.dll.head.next.value == -1:
return ""
for k in self.dll.tail.prev.keys:
break
return k
def getMinKey(self):
if self.dll.head.next.value == -1:
return ""
for k in self.dll.head.next.keys:
break
return k
