队列的例题和总结
0. 目录
1. 栈实现队列
FIFO和FILO，相当于+-号，互转都是利用“负负得正”的原理。
官方解答中第二种思路很6，按需反转，这样摊还分析下来，复杂度变成了O(1)
class MyQueue {
private:
stack<int> s1;
stack<int> s2;
public:
/** Initialize your data structure here. */
MyQueue() {}
/** Push element x to the back of queue. */
void push(int x) {
s1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
int ret=0;
notempty:
if(!s2.empty()){
ret = s2.top();
s2.pop();
return ret;
}
while(!s1.empty()){
s2.push(s1.top());
s1.pop();
}
//return pop();
goto notempty;
}
/** Get the front element. */
int peek() {
int ret=0;
notempty:
if(!s2.empty()) return s2.top();
while(!s1.empty()){
s2.push(s1.top());
s1.pop();
}
goto notempty;
}
/** Returns whether the queue is empty. */
bool empty() {
return s1.empty() && s2.empty();
}
};
2. 队列实现栈
官方解答中提供了三种思路，我用的方法和方法三很像，又同时做了一点点优化：
- 官方方法三
- 入栈O(N)
- 出栈O(1)
- 我的方法四 (其实思路一样, 就是pop时才去排序.)
- 入栈O(1)
- 出栈O(N),
- 方法四的优化
- 入栈O(1)
- 出栈: 最坏的情况O(N)，最好的情况实际pop次数为0
- 缺点: 需要自定义结构体标记
2.1 方法四
class MyStack {
private:
queue<int> buf;
public:
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
buf.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int size = buf.size();
int ret = buf.back();
while(--size>=0){
if(size!=0) buf.push(buf.front());
buf.pop();
}
return ret;
}
/** Get the top element. */
int top() {
return buf.back();
}
/** Returns whether the stack is empty. */
bool empty() {
return buf.empty();
}
};
2.2 方法四的优化版
思路就是：
- 用自定义结构体中的flag成员标记当前队列中元素是否有效, 如果是false，则相当于已经被pop(实际并不用pop)
- push直接添加，略
- pop时
- 如果
back().falg==true，我们直接修改其为false，标记其已经无效了 - 否则，说明倒数两个需要被删除, 按照单队列思路，头循环加到尾部，然后把最后两个都直接pop掉（因为最后一个已经被标记为false，而现在又pop一次，所以两个都直接pop）
- 如果
- top时，类似pop的处理方法
- 最坏的情况：连续pop，但是即使这样pop依然是O(N)
- 最好的情况: push一次,pop一次, 这样实际pop次数为0
- 混合情况: 优于单队列
typedef struct {
int val;
bool flag;
}myint;
class MyStack {
private:
queue<myint> buf;
public:
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
myint mx = {x, true};
buf.push(mx);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
if(buf.back().flag == true) {
buf.back().flag=false;
return buf.back().val;
}
int size = buf.size();
while(--size>=2){
buf.push(buf.front());
buf.pop();
}
int ret = buf.front().val;
buf.pop();
buf.pop();
return ret;
}
/** Get the top element. */
int top() {
if(buf.back().flag==true) return buf.back().val;
int size = buf.size();
while(--size>=1){
buf.push(buf.front());
buf.pop();
}
buf.pop();
return buf.back().val;
}
/** Returns whether the stack is empty. */
bool empty() {
return (buf.empty() || (!buf.front().flag));
}
};
3. 滑动窗口最大值
这个题目确实挺难的，我看了老师的讲解后开始做题，思路是用双端队列(我做了一点点改进)：
- 每次滑动窗口，在往队列中加入新的元素之前，删除那些比它小的元素（因为新元素存活比它们久，有比它们大，所以最大值永远不可能是它们）
- 队列的头部就是我们要找的最大值了
但是还是遇到了不少问题：
- 错误思路一：直接把值当作元素加入到队列中，而不是用索引，这样我就很难知道一个元素是不是已经过了窗口，也就不知道该不该删除了
- 错误思路二：其实不算错, 就是复杂度太高. 这个方法相比官方答案是不删除比新元素小的, 而是把比它小的都改成它一样的值, 这样事情就很简单了, 不过复杂度太高
3.1 错误一：很难标记一个元素是否已经过了k窗口
对比一下就知道我的方法的错误和落后之处了:
- 加入值nums[i]: 只能提供一个信息, 那就是一个数值
- 加入索引值i: 可以提供两个信息:
- 由索引得到值O(1)的复杂度
- 索引本身标记了该元素在原容器中的位置信息, 这样窗口移动时, 我们可以知道该元素是不是还在队列中(该索引值与i-k比较即可)
所以, 为了解决信息不足的问题想了很多办法, 就是没想到索引值:
- 错误解决方法一: 用一个数n记录删除的次数, 每次循环前看看n是不是大于0, 如果是则说明删除过不需要pop_front
- 这个方法被测试有问题的, 例如[1,2,4,2,3,1],3的情况, 移动到[4,2,3]时, 3比2大, 删除一次, num=1, 这时该移动到[2,3,1], 结果因为num大于0, 没有把4剔除导致错误
- 错误解决方法二: 用自定义的结构体加入deque, 另用一个成员标记该元素在deqeu中待的时间
- 其实可行, 但是每移动一次就要为deque中所有元素的成员减一, 复杂度增加不少
3.2 错误思路二: 把比它小的都改成它一样的值, 复杂度太高
直接看我的源码吧:
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k){
vector<int > ret;
ret.reserve((nums.size()-k+1));
vector<int>::iterator iter;
deque<int> deq;
for(iter=nums.begin();iter!=nums.end();++iter){
deq.push_back(*iter);
for(auto jter=deq.begin();jter!=deq.end()-1;++jter){
if(*iter>*jter) {
for(auto kter=jter;kter!=deq.end()-1;++kter)
*kter = *iter;//把所有比它小的都改成和它一样的值
break;
}
}
if(deq.size()<k) continue;
ret.push_back(deq.front());
deq.pop_front();
}
return ret;
}
};
3.3 双端队列改进版
以下是我认为改进的地方
//我认为改进的地方
for(auto jter=deq.begin();jter!=deq.end();++jter){
if(nums[i]>nums[*jter]) {
deq.resize(jter-deq.begin());
break;
}
}
以下摘自大神AdamWong
while (!window.empty() && nums[i] > nums[window.back()]) {
window.pop_back();
}
可以看出我们的区别:
- 我的方法是:如果新数据比window.back小，就从window.front开始依次比较，然后遇到某个比它小的，就把这以后的全部删除（因为前面大，后面更小），然后可以用deque.resize函数直接截断后面的所有。我觉得这样比较的次数会减少, 而且操作resize一次性搞定.
- AdamWong的是: 当我们遇到新的数时，将新的数和双项队列的末尾（也就是window.back()）比较，如果末尾比新数小，则把末尾扔掉，直到该队列的末尾比新数大或者队列为空的时候才停止，做法有点像使用栈进行括号匹配。
我的源码:
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k){
if(nums.size()==1) return {nums[0]};
int i=0;
int maxindex = 0;
for(i=1;i<k;++i){
if(nums[i]>nums[maxindex]) maxindex = i;
}
if(nums.size()==k) return {nums[maxindex]};
deque<int> deq;
vector<int > ret;
ret.reserve((nums.size()-k+1));
ret.push_back(nums[maxindex]);
//初始化deque, 把前k个弄完
deq.push_back(maxindex);
for(i=maxindex+1;i<k;++i){
if(nums[i]<=nums[deq.back()]) {
deq.push_back(i);
continue;
}
for(auto jter=deq.begin();jter!=deq.end();++jter){
if(nums[i]>nums[*jter]) {
deq.resize(jter-deq.begin());
break;
}
}
deq.push_back(i);
}
//正式开始
for(i=k;i<nums.size();++i){
if(deq.front()==i-k) deq.pop_front();
if(nums[i]<=nums[deq.back()]) goto addtoresult;
for(auto jter=deq.begin();jter!=deq.end();++jter){
if(nums[i]>nums[*jter]) {
deq.resize(jter-deq.begin());
break;
}
}
addtoresult:
deq.push_back(i);
ret.push_back(nums[deq.front()]);
}
return ret;
}
};