Problem

Implement an LRU (Least Recently Used) cache with a fixed positive capacity. Design a class that supports get(key) and put(key, value) in O(1) average time. get(key) returns the value if the key exists, otherwise -1. put(key, value) inserts or updates the key; if the cache exceeds capacity, evict the least recently used key.

Examples

Example 1:

Input:
LRUCache(2)
put(1, 1)
put(2, 2)
get(1)
put(3, 3)
get(2)
put(4, 4)
get(1)
get(3)
get(4)

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

Explanation: Accessing key 1 makes it most recently used. Inserting 3 evicts 2, and inserting 4 evicts 1.

Example 2:

Input:
LRUCache(1)
put(2, 1)
get(2)
put(3, 2)
get(2)
get(3)

Output:
[null, null, 1, null, -1, 2]

Explanation: With capacity 1, each new key evicts the previous one.

Constraints

• 1 <= capacity <= 3000
• 0 <= key <= 10^4
• 0 <= value <= 10^5
• At most 2 * 10^5 calls to get and put