哈哈，我用了HashMap, 双向链表，还有了HashSet来保存key的集合。
现在这道题目还只有 9.3%的AC率，难度为Hard Total Accepted: 9Total Submissions: 97Difficulty: Hard
我也把解法发到了Discuss版：
https://discuss.leetcode.com/topic/63559/my-accepted-java-solution-with-hashmap-and-double-linked-list
https://leetcode.com/problems/all-oone-data-structure/class AllOne { // Hashmap for get Node to operate inc and dec // LinkNode to maintain order // HashSet to maintain key with certain value private class LinkNode { public int val; // maintain current value LinkNode small; // maintain link to smaller node LinkNode big; // maintain link to bigger node Set keySet; // maintain keys with current value LinkNode(String key, int v) { keySet = new HashSet<>(); keySet.add(key); val = v; } } private LinkNode maxNode; private LinkNode minNode; Map hmap; /** Initialize your data structure here. */ public AllOne() { hmap = new HashMap<>(); maxNode = null; minNode = null; } /** Inserts a new key with value 1. Or increments an existing key by 1. */ public void inc(String key) { LinkNode lknd; if (hmap.containsKey(key)) { lknd = hmap.get(key); lknd.keySet.remove(key); if (lknd.big != null) { if (lknd.big.val == lknd.val+1) { lknd.big.keySet.add(key); hmap.put(key, lknd.big); } else { LinkNode lbig = new LinkNode(key, lknd.val+1); lbig.small = lknd; lbig.big = lknd.big; lknd.big = lbig; lbig.big.small = lbig; hmap.put(key, lbig); } } else { LinkNode lbig = new LinkNode(key, lknd.val+1); lbig.small = lknd; lknd.big = lbig; maxNode = lbig; hmap.put(key, lbig); } // remove original node if necessary if (lknd.keySet.isEmpty()) { // for minNode if (minNode == lknd) { minNode = lknd.big; } else { lknd.small.big = lknd.big; } // for maxNode if (maxNode == lknd) { maxNode = lknd.small; } else { lknd.big.small =lknd.small; } } } else { if (minNode == null) { // all list is null lknd = new LinkNode(key, 1); minNode = lknd; maxNode = lknd; } else { if (minNode.val != 1) { lknd = new LinkNode(key, 1); lknd.big = minNode; minNode.small = lknd; minNode = lknd; } else { minNode.keySet.add(key); lknd = minNode; } } hmap.put(key, lknd); } } /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */ public void dec(String key) { LinkNode lknd; if (hmap.containsKey(key)) { lknd = hmap.get(key); lknd.keySet.remove(key); if (lknd.val == 1) { hmap.remove(key); } else { if (lknd.small != null) { if (lknd.small.val == lknd.val - 1) { lknd.small.keySet.add(key); hmap.put(key, lknd.small); } else { LinkNode lsmall = new LinkNode(key, lknd.val - 1); lsmall.big = lknd; lsmall.small = lknd.small; lknd.small = lsmall; lsmall.small.big = lsmall; hmap.put(key, lsmall); } } else { LinkNode lsmall = new LinkNode(key, lknd.val - 1); lknd.small = lsmall; lsmall.big = lknd; minNode = lsmall; hmap.put(key, lsmall); } } // remove original node if necessary if (lknd.keySet.isEmpty()) { // for minNode if (minNode == lknd) { minNode = lknd.big; } else { lknd.small.big = lknd.big; } // for maxNode if (maxNode == lknd) { maxNode = lknd.small; } else { lknd.big.small =lknd.small; } } } } /** Returns one of the keys with maximal value. */ public String getMaxKey() { if (maxNode == null) { return ""; } Iterator iter = maxNode.keySet.iterator(); return iter.next(); } /** Returns one of the keys with Minimal value. */ public String getMinKey() { if (minNode == null) { return ""; } Iterator iter = minNode.keySet.iterator(); return iter.next(); } public void printAll() { LinkNode tmp = maxNode; System.out.println("Start print"); if (tmp != null) { System.out.printf("Node val: %d\n", tmp.val); Iterator iter = tmp.keySet.iterator(); while (iter.hasNext()) { System.out.printf("key: %s,", iter.next()); } System.out.println(); tmp = tmp.small; } if (minNode != null) { System.out.printf("Min Node val: %d\n", minNode.val); Iterator iter = minNode.keySet.iterator(); while (iter.hasNext()) { System.out.printf("key: %s,", iter.next()); } System.out.println(); } System.out.println("End print"); }} /** * Your AllOne object will be instantiated and called as such: * AllOne obj = new AllOne(); * obj.inc(key); * obj.dec(key); * String param_3 = obj.getMaxKey(); * String param_4 = obj.getMinKey(); */