大型网站技术方案唐山网络运营推广

链接：

剑指 Offer 59 - II. 队列的最大值

题意：

如题，要求O1给出数列的最大值

解：

类似滑动窗口

1 1 2 1 2用双端队列存储成2 2（每次从前面获取最大值，后面插入新数字）也就是第一个2覆盖了前面两个1，第二个2覆盖了一个1

1 1 2 3 2存储成3 2因为在抛弃到3之前3都是队列内最大的，移除前面的和最大值3无关，直到移除3

核心思想，越后面进入队列的数字存在时间越久，存在久的数字可以替换小于它的存在短的数字；移除最大数字前面的数字对最大值没有影响，直到移除最大的数字以后更新成次大数

实际代码：

#include<bits/stdc++.h>
using namespace std;
class MaxQueue
{
public:MaxQueue() =default;//默认构造 int max_value(){if(Max.empty()) return -1;else return Max.front();}//获取最大值 void push_back(int value){qe.push(value);while(!Max.empty()&& value>Max.back()) Max.pop_back();Max.push_back(value);}//压入队列 int pop_front(){if(qe.empty()) return -1;int ret=qe.front();qe.pop();if(ret==Max.front()) Max.pop_front();return ret;}//抛出队列 
private:queue<int>qe;deque<int>Max;
};
int main()
{}

限制：

• 1 <= push_back,pop_front,max_value的总操作数 <= 10000
• 1 <= value <= 10^5