1、最小栈
题目连接
题目描述：
示例：
输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
说明：
pop、top 和 getMin 操作总是在非空栈上调用。
解题思路：
创建两个栈，一个栈q完成正常的插入删除操作，另外一个栈min_st存栈的最小值，其栈顶就是当前st中所有数据的最小值。
插入数据：
- st直接插入。
- max_st如果为空也是直接插入，不空的话把插入数据和其栈顶数据比较，如果小于等于栈顶数据就插入，大于就不插入。
删除数据：
- st直接删除。
- 如果st的栈顶数据等于min_st的栈顶数据，那么min_st也出栈，否则不出栈。
完整代码：
class MinStack { private: stack<int>st; // 用来存储栈元素 stack<int>min_st; // 用来存储栈最小元素 public: MinStack() {} void push(int val) { st.push(val); // 如果min_st为空或者val小于等于min_st栈顶元素min_st都要入栈，来记录当前最小元素 if(min_st.empty() || val<=min_st.top()) { min_st.push(val); } } void pop() { // 如果st的栈顶等于min_st栈顶，两者都要出栈 if(st.top() == min_st.top()) { min_st.pop(); } st.pop(); } int top() { return st.top(); } int getMin() { return min_st.top(); } };
性能分析：
- 时间复杂度：O(1)。各个操作都一次完成。
- 空间复杂度：O(n)。用到了两个栈，每个栈最多都插入n次。
2、剑指 Offer 59 - II. 队列的最大值
题目连接
题目描述：
示例1：
输入:
[“MaxQueue”,“push_back”,“push_back”,“max_value”,“pop_front”,“max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例2：
输入:
[“MaxQueue”,“pop_front”,“max_value”]
[[],[],[]]
输出: [null,-1,-1]
限制：
- 1 <= push_back,pop_front,max_value的总操作数 <= 10000
- 1 <= value <= 10^5
解题思路：
创建一个队列q，原来完成基本的队列操作。再创建一个双端队列max_dq存队列的最大值，其队头数据就是当前q队列的最大值。
入队列：
- q直接入队列
- max_dq为空也是直接入队列。不为空的话，考虑到队列是头出尾进，现在这个值已经入了队列q的尾部
- 如果该值大于max_dq.front()，那它就是q中所有数据的最大值。这时我们清空max_dq的内容，并把值插入到max_dq，更新队列的最大值。
- 如果该值小于max_dq.front()，即该值比未入队列q前的原来数据的最大值还小，但它可能是原来数据全出队列后的最大值，所以我们要考虑把他插入到max_dq的尾部，即从max_dq尾部排除其他小于该值的数据后尾插该值。
出队列：
- q的话直接出队列。
- max_dq，比较q.front()是否等于max_dq.front()，相等的话max_dq就出，否则不出。
完整代码：
class MaxQueue { private: queue<int> q;// 普通的队列 deque<int> max_dq;// 存放最大值的双端队列 public: MaxQueue() {} int max_value() { return max_dq.size()==0?-1:max_dq.front(); } void push_back(int value) { q.push(value); if(value > max_dq.front()) { max_dq.clear(); max_dq.push_back(value); } else { while(!max_dq.empty() && (max_dq.back()<value)) { max_dq.pop_back(); } max_dq.push_back(value); } } int pop_front() { if(q.empty()) { return -1; } if(q.front() == max_dq.front()) { max_dq.pop_front(); } int ret=q.front(); q.pop(); return ret; } };
性能分析：
- 时间复杂度：O(1)。虽然插入操作中有循环，但每个元素只会入队列一次、出队列一次，循环中的出队列次数均摊到入队列，肯定不会大于N次，所以最后平均下来就是O(1)。
- 空间复杂度：O(n)。用到两个队列，每个最多插入n个元素。
3、设计循环队列
题目连接
题目描述：
示例：
提示：
- 所有的值都在 0 至 1000 的范围内；
- 操作数将在 1 至 1000 的范围内；
- 请不要使用内置的队列库。
解题思路：
循环队列就是指定空间大小，并能充分利用这些空间来实现队列基本功能的队列。既要求非动态又要满足队列的基本功能，我们可以考虑使用数组作为底层容器，因为它可以快速进行随机访问。
1.循环方法
我们构造两个整型变量head和tail分别指向队头和队尾的下标
- 入队列的话就是在tail位置处赋值，完成后tail往后移动一个位置。
- 出队列的话head往后移动一个位置即可。
但因为要满足循环，即head或tail如果在数组最后一个位置，再往后移动就是回到下标为0处，而不能直接+1。通常我们会想特殊判断并处理最后一个位置处的后移。其实没必要，后移只需：（当前下标 + 1）%数组长度。
2.容量问题
假设要求循环队列长度为k，那么我们应该给数组开多大空间呢？首先开k个是不行的，这样不能很好的区分队列是空还是满。
既然问题在于判空和判满的条件冲突了，那我们就开k+1个空间的数据。这时判空的条件依然是head == tail，判满的条件为：(tail+1)%(k+1) == head。
完整代码：
class MyCircularQueue { private: vector<int> _q;// 队列主体 int _allSize;// 记录队列总长度 int _head; int _tail; public: MyCircularQueue(int k) :_q(k+1) ,_allSize(k+1) ,_head(0) ,_tail(0) {} bool enQueue(int value) { if(isFull()) { return false; } _q[_tail] = value; _tail = (_tail+1)%_allSize; return true; } bool deQueue() { if(isEmpty()) { return false; } _head = (_head+1)%_allSize; return true; } int Front() { if(isEmpty()) { return -1; } return _q[_head]; } int Rear() { if(isEmpty()) { return -1; } int prevTail = _tail - 1; if(!(_tail)) { prevTail = _allSize - 1; } return _q[prevTail]; } bool isEmpty() { return _head == _tail; } bool isFull() { return (_tail + 1)%_allSize == _head; } };
性能分析：
时间复杂度：O(1)。每一个步骤都可以在常数时间内完成。
空间复杂度：O(n)。n是队列的预分配容量。循环队列的整个生命周期中，都持有该预分配的空间。
-4、LRU 缓存机制
题目连接
题目描述：
示例：
说明：
解题思路：
下面讨论在 O(1) 时间复杂度内完成这两种操作的方法。
首先元素类型是pair键值对，为了达到O(1)的插入删除我们选择用list来存储这些键值对：
- list<pair<int, int>> _LRUList;
为了达到O(1)的查找效率，考虑用哈希表来存键值对：
- unordered_map<int, pair<int, int>> _um;
说明一下，上面定义的结构是达不到O(1)的执行效率的，原因如下：
既然问题出在调整链表中节点顺序的时间复杂度不够，即不能快速定位到关键字为key的节点在哪，可以考虑让哈希表_um的second存储关键字为key的节点的迭代器，这样通过_um可以快速搜索到对应节点，即可以方便调整链表中节点的位置，也可以通过节点拿到key对应的value。
确定好结构之后，只需解决put()和get()两种操作的实现：
1、int get(int key)
如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
- 通过_um查找key，找到的话要返回value并更新链表中key节点为最近使用的，这里可以通过splice()接口把节点转移到链表最后位置。
- 找不到的话返回-1。
int get(int key) { auto it = _um.find(key); if(it != _um.end()) { _LRUList.splice(_LRUList.end(), _LRUList, it->second); return it->second->second; } else { return -1; } }
2、void put(int key, int value)
- 通过_um查找key，如果key不存在，插入键值对并在链表中更新key为最近使用的。注意如果容量满了，还要删除最久未使用的。
- 如果key存在，更新其value并把key置为最近使用的。
void put(int key, int value) { auto it = _um.find(key); if(it != _um.end()) { it->second->second = value; _LRUList.splice(_LRUList.end(), _LRUList, it->second); } else { if(_LRUList.size() == _capacity) { _um.erase(_LRUList.begin()->first); _LRUList.erase(_LRUList.begin()); } _LRUList.push_back(make_pair(key, value)); _um[key] = --_LRUList.end(); } }
完整代码：
class LRUCache { private: size_t _capacity; list<pair<int, int>> _LRUList; unordered_map<int, list<pair<int, int>>::iterator> _um; public: LRUCache(int capacity) :_capacity(capacity) {} int get(int key) { auto it = _um.find(key); if(it != _um.end()) { _LRUList.splice(_LRUList.end(), _LRUList, it->second); return it->second->second; } else { return -1; } } void put(int key, int value) { auto it = _um.find(key); if(it != _um.end()) { it->second->second = value; _LRUList.splice(_LRUList.end(), _LRUList, it->second); } else { if(_LRUList.size() == _capacity) { _um.erase(_LRUList.begin()->first); _LRUList.erase(_LRUList.begin()); } _LRUList.push_back(make_pair(key, value)); _um[key] = --_LRUList.end(); } } };
性能分析：
- 时间复杂度：对于 put 和 get 都是 O(1)。
- 空间复杂度：O(capacity)。因为哈希表和双向链表最多存储capacity个元素。
