RMQ(x, y)就是询问数组在[x, y]区间内不得最小值
对于下面这个数组来说RMQ(0, 3) = 1
4个！[1, 2, 8, 12]即可
但是我们惊奇的发现这四个值形成了一个单增的序列！
如果有一个额外的数据结构记录这四个值
那么这个数据结构有如下性质：
- 元素单调
- 元素之间的相对位置和原序列保持一致
一般都配合滑动窗口使用
单调队列头部一定是记录的滑动窗口的min
维护区间min的队列一定是一个单增队列
因为队列的头部元素才是我们要维护的值
（每次是pop_front）
所以头部元素一定是最小的--也就是单增
这时候滑动窗口向后走一问，滑动窗口变成了4, 5, 2
为了保证队列的单调性，2需要把4 5踢出去
因为当前滑动窗口的最小值是2，
也就是说4，5不管怎么滑，都不可能是min了
（前面有1，后面有2）
并且因为1超出了滑动窗口的边界，把1也踢出去
......
一直到滑动窗口移动到末尾
这时候如果加上前面弹出的1, 2，形成的序列正好能解决上面的RMQ问题
哎 为啥1 2会被踢出去？因为超出了滑动窗口的范围
再次强调：单调队列适合维护滑动窗口（区间）最值问题
并且我们发现如果改变RMQ末尾元素的值
也正好能和求解RMQ问题的对应的中间状态配上
这里要明确
单调队列是为了解决RMQ的问题而衍生出来的数据结构
并且滑动窗口的大小和RMQ的大小无关，单调队列的元素数量也和滑动窗口大小无关。它只会在超出滑动窗口的时候踢出队首元素
队尾入队，会把之前破坏单调性的元素都从队尾移出（维护单调性）
如果队首元素超出区间范围，就将元素从队首出队
队首元素，永远是当前维护区间的（最大/最小）值
序列中的每一个元素，在依次入队的过程中，每个元素都『黄』过
维护最小元素是单增队列，维护最大元素是单减队列
因为队首元素都是最小啦，后面的肯定比他要大！
经典RMQ问题
get编程技巧记录源信息（在这个里面是数组下标）
int main(int argc, char **argv) {
int n, k;
std::vector<int> arr;
std::cin >> n >> k;
for (int i = 0, a; i < n; i++) {
std::cin >> a;
arr.push_back(a);
}
std::deque<int> q;
for (int i = 0; i < n; i++) {
// 入队列 -> 维护单调性
// 先判断队尾元素是否违反单调性
while (!q.empty() && arr[q.back()] > arr[i]) q.pop_back();
q.push_back(i);
// 下面进行滑动窗口越界头部元素的弹出
// 但是queue中记录的是元素的值
// 通过值可没法求滑动窗口的长度哎！
// 所以存下标就可
// 出队列 -> 维护元素生命周期
if (i - q.front() == k) q.pop_front();
if (i + 1 < k) continue;
(i + 1 > k) && std::cout << " ";
std::cout << arr[q.front()];
}
std::cout << std::endl;
q.clear();
for (int i = 0; i < n; i++) {
while (!q.empty() && arr[i] > arr[q.back()]) q.pop_back();
q.push_back(i);
if (i - q.front() == k) q.pop_front();
if (i + 1 < k) continue;
// 因为第一次输出的时候是i + 1 == k
// 即滑动窗口刚好 == k
// 这样能除去多余的空格
(i + 1 > k) && std::cout << " ";
std::cout << arr[q.front()];
}
std::cout << std::endl;
return 0;
}单调队列只有front有特性，尾巴没有特性，这也就是为什么输出front就行了
u，v 两个序列趋势相同，当且仅当对于任意 l 和 r，均有RMQ(u,l,r)=RMQ(v,l,r) (1≤l≤r≤n)
这不就说明了任意位置固定r的RMQ相等么
那不就是他们对应的单调序列每个元素都相等！
所以模拟一遍构建单调队列的过程，找出第一个不同的位置，那不就是p了
并且还是存下标哦，因为p是长度
并且这个题没有滑动窗口，所以就不用pop_front了，相对来说处理起来更简单
int main(int argc, char **argv) {
int n;
std::cin >> n;
std::vector<int> a, b;
for (int i = 0, aa; i < n; i++) {
std::cin >> aa;
a.push_back(aa);
}
for (int i = 0, bb; i < n; i++) {
std::cin >> bb;
b.push_back(bb);
}
std::deque<int> q1, q2;
int p;
for (p = 0; p < n; p++) {
// 最小值 构建单增队列
while (q1.size() && a[p] < q1.back()) q1.pop_back();
while (q2.size() && b[p] < q2.back()) q2.pop_back();
q1.push_back(a[p]);
q2.push_back(b[p]);
// 证明找到了第一个不同的p！
// 也就是单调队列的元素个数
// 因为p指向的位置（a，b）肯定是一样的
// 但是能不能加入q就看符合RMQ的性质
if (q1.size() != q2.size()) break;
}
std::cout << p << std::endl;
return 0;
}