数据结构——队列¶
两个栈实现队列¶
- LeetCode 232.用栈实现队列
使用栈实现队列的下列操作：
push(x)-- 将一个元素放入队列的尾部。pop()-- 从队列首部移除元素。peek()-- 返回队列首部的元素。empty()-- 返回队列是否为空。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
class MyQueue {
stack<int> s1, s2;
public:
/** Initialize your data structure here. */
MyQueue() {}
/** Push element x to the back of queue. */
void push(int x) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
s1.push(x);
while (!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
int res = s1.top();
s1.pop();
return res;
}
/** Get the front element. */
int peek() {
return s1.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return s1.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
两个队列实现栈¶
- LeetCode 225.用队列实现栈
使用队列实现栈的下列操作：
push(x)-- 元素 x 入栈pop()-- 移除栈顶元素top()-- 获取栈顶元素empty()-- 返回栈是否为空
class MyStack {
queue<int> q1, q2;
public:
/** Initialize your data structure here. */
MyStack() {}
/** Push element x onto stack. */
void push(int x) {
while (!q1.empty()) {
q2.push(q1.front());
q1.pop();
}
q1.push(x);
while (!q2.empty()) {
q1.push(q2.front());
q2.pop();
}
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int res = q1.front();
q1.pop();
return res;
}
/** Get the top element. */
int top() {
return q1.front();
}
/** Returns whether the stack is empty. */
bool empty() {
return q1.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
循环队列¶
- LeetCode 622: 设计你的循环队列实现。
循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
class MyCircularQueue {
vector<int> num;
int start, end; //记录首尾位置
int len;
public:
/** Initialize your data structure here. Set the size of the queue to be k. */
MyCircularQueue(int k) {
num.resize(k);
start = end = len = 0;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
bool enQueue(int value) {
int n = num.size();
//如果队列已满
if (len == n) return false;
//队列未满
if (!len) {
num[start] = value;
++len;
}
else {
end = (end + 1) % n;
num[end] = value;
++len;
}
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
bool deQueue() {
//如果队列为空，无元素可删
if (!len) return false;
//队列中存在元素
int n = num.size();
if (start == end) {
--len;
}
else {
start = (start + 1) % n;
--len;
}
return true;
}
/** Get the front item from the queue. */
int Front() {
if (!len) return -1;
return num[start];
}
/** Get the last item from the queue. */
int Rear() {
if (!len) return -1;
return num[end];
}
/** Checks whether the circular queue is empty or not. */
bool isEmpty() {
return !len;
}
/** Checks whether the circular queue is full or not. */
bool isFull() {
return len == num.size();
}
};
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue* obj = new MyCircularQueue(k);
* bool param_1 = obj->enQueue(value);
* bool param_2 = obj->deQueue();
* int param_3 = obj->Front();
* int param_4 = obj->Rear();
* bool param_5 = obj->isEmpty();
* bool param_6 = obj->isFull();
*/
循环双端队列¶
- LeetCode 641.设计循环双端队列
设计实现双端队列。 你的实现需要支持以下操作：
MyCircularDeque(k)：构造函数,双端队列的大小为k。insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。isEmpty()：检查双端队列是否为空。isFull()：检查双端队列是否满了。
class MyCircularDeque {
vector<int> num;
int n;
int start, end, len;
public:
/** Initialize your data structure here. Set the size of the deque to be k. */
MyCircularDeque(int k) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
num.resize(k);
n = k;
start = end = len = 0;
}
/** Adds an item at the front of Deque. Return true if the operation is successful. */
bool insertFront(int value) {
if (len == n) return false;
if (!len) {
num[start] = value;
++len;
}
else {
start = (start - 1 + n) % n;
num[start] = value;
++len;
}
return true;
}
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
bool insertLast(int value) {
if (len == n) return false;
if (!len) {
num[end] = value;
++len;
}
else {
end = (end + 1) % n;
num[end] = value;
++len;
}
return true;
}
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
bool deleteFront() {
if (len == 0) return false;
if (start == end) --len;
else {
start = (start + 1) % n;
--len;
}
return true;
}
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
bool deleteLast() {
if (len == 0) return false;
if (start == end) --len;
else {
end = (end - 1 + n) % n;
--len;
}
return true;
}
/** Get the front item from the deque. */
int getFront() {
if (len == 0) return -1;
return num[start];
}
/** Get the last item from the deque. */
int getRear() {
if (len == 0) return -1;
return num[end];
}
/** Checks whether the circular deque is empty or not. */
bool isEmpty() {
return len == 0;
}
/** Checks whether the circular deque is full or not. */
bool isFull() {
return len == n;
}
};
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque* obj = new MyCircularDeque(k);
* bool param_1 = obj->insertFront(value);
* bool param_2 = obj->insertLast(value);
* bool param_3 = obj->deleteFront();
* bool param_4 = obj->deleteLast();
* int param_5 = obj->getFront();
* int param_6 = obj->getRear();
* bool param_7 = obj->isEmpty();
* bool param_8 = obj->isFull();
*/
单调队列¶
单调队列的常用应用有：参考链接：https://blog.csdn.net/u011815404/article/details/86896303
- 维护单调性，从而解决区间内最小/大的问题
- 优化多重背包 DP、斜率优化 DP
单调队列解决区间最大/最小值¶
单调队列也叫滑动窗口，在《挑战程序设计竞赛》的4.4.2节有涉及。
- LeetCode 239.Sliding Window Maximum。
- 洛谷-P1886 滑动窗口 /【模板】单调队列
- POJ 2823 Sliding Window（单调队列模板，注意选G++编译，C++编译会TLE）
- POJ 3709 K-Anonymous Sequence（来自《挑战程序设计竞赛》）
- 最大子序和（来自《算法竞赛进阶指南》）
- 洛谷-P1440 求m区间内的最小值（单调队列模板题）
- LeetCode 1437.Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
Example:
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Note: You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.
Follow up: Could you solve it in linear time?
这道题目当然可以用ST表版本的RMQ或线段树版本的RMQ，但是利用其查询窗口固定，查询顺序自前向后的这一特点，可以利用最适合的单调队列来求解。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int> res;
deque<int> q;
for (int i = 0; i < nums.size(); ++i) {
if (!q.empty() && q.front() == i - k) q.pop_front();
while (!q.empty() && nums[q.back()] < nums[i]) q.pop_back();
q.push_back(i);
if (i >= k - 1) res.push_back(nums[q.front()]);
}
return res;
}
};
使用数组模拟双端队列。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int> res;
vector<int> dq_pos(100005);
int n = nums.size();
int start = 0, end = 0;
for (int i = 0; i < n; ++i) {
if (start < end && dq_pos[start] == i - k) ++start;
while (start < end && nums[dq_pos[end - 1]] <= nums[i]) --end;
dq_pos[end++] = i;
if (i >= k - 1) res.push_back(nums[dq_pos[start]]);
//if (dq_pos[start] == i - k) ++start;
}
return res;
}
};
这里容易产生的错误时17行的程序，面对下面的例子会错误：
nums = [1, -1] k = 1
问题的根源不在队列长度和k的比较的语句放在前面和放在后面，而是它们表示的意义不一样。当判断放在最后，意味着在判断下一个元素是否进队之前，总保证队列里有空余的位置，而放在最前面是先保证有空余位置，然后再判断元素是否入队。所以如果想让17行的程序起作用，只需改为i + 1 - k即可，另外，在14行的判断符号上，<=和<都是可行的，并不影响结果。
另外如果很难判断究竟放在最前面判断和最后面判断什么时候该+1，什么时候该-1，可以让k=1进行判断，就很容易的进行检验。
单调队列优化多重背包¶
- 一本通-1269：【例9.13】庆功会
- 洛谷-P1776 宝物筛选
- HDU 1171 Big Event in HDU
假设物品的种类为n，背包容量为m，每个物品的重量为w[i]，价值为value[i]，数量为num[i]，用d[j]代表背包容量为j时所能得到的最大值。则：
$$
d[j] = \max_{0 \leq k \leq num[i] \&\& j - k \times w[i] \geq 0} (d[j - k\times w[i]] + value[i])
$$
在进行状态转移的时候，j的状态只受到j - w[i], j - 2*w[i] ...的影响，对于j-1，其状态和j的状态互不影响，于是我们可以根据j % w[i]的余数进行分组，余数相同的必在一组。现在假设w[i] = 3，那么根据余数可以分成3组：
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | \cdots |
|---|---|---|---|---|---|---|---|---|---|---|
j mod w[i] |
0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | \cdots |
余数（记为a）相同的组成一组，然后重新编号，单独处理：
编号j |
0 | 1 | 2 | 3 | 4 | 5 | \cdots |
|---|---|---|---|---|---|---|---|
| 对应重量 | a | a+w[i] | a+2*w[i] | a+3*w[i] | a+4*w[i] | a+5*w[i] | \cdots |
如果没有物品数量的限制，则编号为5的可以由编号为0,1,2,3,4状态转移过来，但是因为有数量限制的存在，那么其实相当于增加了一个长度为num[i]的窗口，这个窗口从前往后滑动，然后求取窗口内的最大值，于是想到可以用单调队列来完成这一工作。
我们令： $$ a = j \mod w[i], b = \left[\frac{j-a}{w[i]}\right] \ j = b \times w[i] + a \ 令k^{'} = b - k; \ d\left[j - k\times w[i]\right] + value[i] = d\left[a +k^{'}\times w[i]\right] - k^{'}\times value[i] + a\times value[i] \ 0 \leq k \leq \min(\left[\frac{j-a}{w[i]}\right], num[i]) \ \max(0, b - num[i]) \leq k^{'} \leq b \ $$
//一本通-1269：【例9.13】庆功会
#include <bits/stdc++.h>
using namespace std;
vector<int> price(505), value(505), num(505);
int n, m;
vector<int> dq_pos(6005), dq_val(6005); //模拟双端队列
vector<int> d(6005);
int multiPack()
{
for (int i = 0; i < n; ++i) {
//通过余数进行分组
for (int a = 0; a < price[i]; ++a) {
int start = 0, end = 0; //双端队列的头尾
for (int j = 0; j * price[i] + a <= m; ++j) {
//if (start < end && dq_pos[start] == j - 1 - num[i]) ++start;
int tmp = d[a + j * price[i]] - j * value[i];
//保证队列单增
while (start < end && dq_val[end - 1] <= tmp) --end;
//新元素加入队列
dq_pos[end] = j;
dq_val[end++] = tmp;
//更新最大值
d[a + j * price[i]] = dq_val[start] + j * value[i];
//如果窗口长度大于num[i]，删掉首部元素
if (dq_pos[start] == j - num[i]) ++start;
}
}
}
return d[m];
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; ++i) cin >> price[i] >> value[i] >> num[i];
cout << multiPack() << endl;
return 0;
}
和LeetCode 239对比，发现29行只需要写成j - num[i]，这个要从窗口长度k的意义来分析，LeetCode 239中窗口长度k是包含当前元素本身的，而我们这里的k表示当前元素前面k个元素转移过来，仍然是让窗口长度为1，那么当j = 1的时候，可以从j = 0转移过来，由于已经处理完成，队列长度又和窗口长度相同，所以这时候需要清空队列了。
单调队列优化动态规划¶
其实单调队列优化背包本身就是优化动态规划，但是因为其优化多重背包太出名了，所以单独拿出来分析。
- LeetCode 918.Maximum Sum Circular Subarray
http://hzwer.com/category/algorithm/dp/decision-monotone
辅助队列实现二叉树层序遍历¶
- LeetCode 102.二叉树的层序遍历
另外队列在BFS中经常被用到。
典型题目
- LeetCode 239.Sliding Window Maximum
- P1886 滑动窗口 /【模板】单调队列
- 一本通-1191：流感传染（两个队列模拟BFS）
- POJ 2259 Team Queue （基础队列模拟 + 哈希）
- 一本通-1334：【例2-3】围圈报数（数组模拟循环链表或者队列模拟）
- 洛谷-P1776 宝物筛选（单调队列优化多重背包）
- 一本通-1269：【例9.13】庆功会（单调队列优化多重背包）
- P6033 合并果子 加强版（基数排序+单调队列+输入输出优化）
- P2827 蚯蚓（单调队列+延迟修改）