8.22 - hard - 84

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