LRU Cache

Build a data structure that behaves as a Least Recently Used (LRU) cache.

Implement the LRUCache class with the following operations:

• LRUCache(int capacity) Creates an LRU cache whose positive maximum size is capacity.
• int get(int key) Produces the value associated with key when it is present; otherwise, it produces -1.
• void put(int key, int value) Replaces the value when key is already stored. If it is absent, insert the key-value pair. When this insertion causes the number of keys to exceed capacity, remove the key that was used least recently.

Both get and put must have O(1) average running time.

Examples

Example 1:

Input: `["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]`

Output: [null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation:

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // the cache now contains {1=1}
lRUCache.put(2, 2); // the cache now contains {1=1, 2=2}
lRUCache.get(1); // produces 1
lRUCache.put(3, 3); // key 2 is least recently used, so it is removed; the cache becomes {1=1, 3=3}
lRUCache.get(2); // produces -1 because key 2 is absent
lRUCache.put(4, 4); // key 1 is least recently used, so it is removed; the cache becomes {4=4, 3=3}
lRUCache.get(1); // produces -1 because key 1 is absent
lRUCache.get(3); // produces 3
lRUCache.get(4); // produces 4

Constraints

• 1 <= capacity <= 3000
• 0 <= key <= 10^4
• 0 <= value <= 10^5
• The combined number of calls to get and put will not exceed 2 * 10^5.