# 常见数据结构设计 ## [LRU Cache](https://leetcode.com/problems/lru-cache/) 一道非常亲切熟悉的题，当初刷 lintcode 的时候非常喜欢这道。这道题因为细节很多，但是操作重复性高，所以非常适合先把流程写下来，然后用 helper 函数实现。 ### 一句话描述这题的话，就是一个 “头 + 尾 dummy node 的双向链表” + “HashMap”. * **先沟通各种 input/output** * **思考流程** * **把流程用 comments (另一种颜色 mark 笔写下来)** * **把发现流程中重复率高的地方写成 function** * **模块化填充，改错。** ```java public class LRUCache { private class Node{ int key; int value; Node prev; Node next; public Node(int key, int value){ this.key = key; this.value = value; } } private int capacity; private HashMap map; // Head : Most recently used private Node dummyHead; // Tail : Least recently used private Node dummyTail; public LRUCache(int capacity) { this.capacity = capacity; this.map = new HashMap(); dummyHead = new Node(-1,-1); dummyTail = new Node(-1,-1); dummyHead.next = dummyTail; dummyTail.prev = dummyHead; } public int get(int key) { if(!map.containsKey(key)) return -1; // Get current node Node node = map.get(key); // Disconnect it from the linkedlist node.prev.next = node.next; node.next.prev = node.prev; // Move it to the front moveToFront(node); // Return value return node.value; } public void set(int key, int value) { if(map.containsKey(key)){ // Get current node Node node = map.get(key); // Disconnect it from the linkedlist node.prev.next = node.next; node.next.prev = node.prev; // Move it to the front moveToFront(node); // set value node.value = value; } else { if(map.size() >= capacity){ // Remove LRU element and its key removeLRU(); } // Create new node Node node = new Node(key, value); // Save its key in map map.put(key, node); // Move it to the front moveToFront(node); } } private void moveToFront(Node node){ Node oldHead = dummyHead.next; // Connect node to dummyHead dummyHead.next = node; node.prev = dummyHead; // Connect node to oldHead node.next = oldHead; oldHead.prev = node; } private void removeLRU(){ Node node = dummyTail.prev; // Disconnect node from linkedlist node.prev.next = node.next; node.next.prev = node.prev; // Set null of its pointers node.next = null; node.prev = null; // Remove its key from hashmap map.remove(node.key); } } ``` ## [Find Median from Data Stream](https://leetcode.com/problems/find-median-from-data-stream/) 也是非常经典的题。 * new PriorityQueue<>(Collections.reverseOrder()); * 把所有数字分成两个区间，一个区间为 <= median 的，存在 maxHeap 里；另一个为 >= median 的，存在 minHeap 里，这样我们每次在堆顶看到的都是 median candidates. * 因此在插入新元素的时候，如果发现其 <= maxHeap top，则说明它位于左区间，插入 max; 反之则插入 minHeap 所代表的右区间。 * 每次新元素插入之后要保持平衡，堆顶的元素切换其实代表着区间分界线的转移。 ```java public class MedianFinder { // max heap stores all elements smaller / equal to median PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); // min heap stores all elements bigger / equal to median PriorityQueue minHeap = new PriorityQueue(); // Adds a number into the data structure. public void addNum(int num) { // Check heap top if(maxHeap.size() == 0 || num <= maxHeap.peek()){ maxHeap.offer(num); } else { minHeap.offer(num); } // min/max heap's size would not differ more than one // Rebalance if necessary while(Math.abs(maxHeap.size() - minHeap.size()) > 1){ if(maxHeap.size() > minHeap.size()){ minHeap.offer(maxHeap.poll()); } else { maxHeap.offer(minHeap.poll()); } } } // Returns the median of current data stream public double findMedian() { int maxSize = maxHeap.size(); int minSize = minHeap.size(); if(maxSize == minSize) return (double) (maxHeap.peek() + minHeap.peek()) / 2; if(maxSize - 1 == minSize) return (double) maxHeap.peek(); if(maxSize == minSize - 1) return (double) minHeap.peek(); return 0; } }; ``` ## [Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/) ### 操作特点： * **只关心区域内的 max;** * **只要同一区域内 max 一样，输出就一样，不在意元素的出现顺序，因此这题有别于 max/min stack 的保存元素顺序要求。** 这题暴力循环可以 O(nk)，hasheap 可以 O(n log k)，deque 可以 O(n). 我们每一步要执行下面三个操作： * 添加当前元素 nums\[i]; * 删除指定元素 nums\[i - k]; * 找到当前 window max; 暴力解法中，我们可以直接维护一个 list，每次操作都进行扫描，这样的复杂度是： * Add O(1) * Remove O(k) * max O(k) 另一种选择是，维护一个 sorted list，这样的复杂度是： * Add O(k) * Remove O(k) * max O(1) 再观察题目特性可以发现，我们在维护 sorted list 上有很多可以取巧的地方： * 因为我们只关心每个 window 上的 max，因此没有必要把 window 内的所有元素都留着，在 Add 的时候可以直接把小于新元素的值都 pop 掉； * 而在 remove 上，对最终结果会产生影响的，只有我们 remove 的元素就是 max 的情形，因为其他无关元素在 add 的时候就被拿掉了；因此我们可以存一个元素的相对位置，以此来判断我们要删掉的元素是不是当前的 max. * 因为我们维护的是 sorted array ，max 依然是 O(1). * 由于每一个元素只会被 add 和 remove 一次，整个流程的均摊复杂度就是 O(1). ### 要点： * **维护一个可以双向操作的 sorted array.** * **Deque 里面要存 index，而不是值，不然会出现 \[8,1,2,8...] 这种情况下，我们有可能会把刚加进去的 8 又给拿出来的 bug.** ```java public class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(nums == null || nums.length == 0) return new int[0]; int[] rst = new int[nums.length - k + 1]; // Deque stores indexes of elements i, in descending order of nums[i] // First : smallet element in current window // Last : biggest element in current window Deque deque = new LinkedList<>(); for(int i = 0; i < nums.length; i++){ while(!deque.isEmpty() && nums[i] > nums[deque.peekFirst()]){ deque.pollFirst(); } deque.offerFirst(i); // element to remove from sliding window if(i - k == deque.peekLast()) deque.pollLast(); if(i - k + 1 >= 0) rst[i - k + 1] = nums[deque.peekLast()]; } return rst; } } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://mnunknown.gitbook.io/algorithm-notes/shu_ju_jie_gou_de_li_yong_ff0c_chu_li_steam_data.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.