"> wennitao爱炒股（一道单调队列题） | Stillwtm's Blog

Stillwtm's Blog
0%

wennitao爱炒股（一道单调队列题）

发表于 更新于 分类于 阅读数： 评论数：
本文介绍一道值得单调队列初学者思考的题目

本文介绍一道值得单调队列初学者思考的题目

原题

题目描述

wennitao喜欢炒股。他仔细研究了一只股票的走势，成功预言了未来 $n$ 天内这支股票每天的价格区间。

具体来说，第$i$天这支股票的价格会在$l_i, r_i$范围内。

wennitao想知道这支股票最长可能保持不跌的天数。

（即最大化天数$k$，使得在这$k$天中，至少存在一种股票价格的情况在满足预测的同时价格不降）

输入格式

第一行一个整数$n$。

接下来$n$行，每行两个整数，第$i$行的两个整数分别表示$l_i, r_i$。

输出格式

输出一行整数，表示满足条件的最长的天数。

样例输入
1
2
3
4
5
6
7
6
6 10
1 5 
4 8 
2 5
6 8 
3 5
样例输出
1
4

原始思路

先将题目进行一个简化，对于一个给定的起点，如果想要存在连续不降的最长序列，那么显然的策略是让每一天的股票价格都保持在一个尽量低的水平，具体来说，第$i$天的价格应该是$min\{第i天的价格, low_i\}$。这是一个容易想到的贪心策略。

那么最简单的思路自然是直接模拟了，即从每个位置开始都进行一次向后遍历，不断进行检查，直至不满足条件为止，并用这次的答案更新最大值。时间复杂度$O(n^2)$。

这显然是不够的，但是时间主要浪费在哪里了呢？重复的检查！可以思考一下，如果已经确定一个区间内存在可行的不降序列，但是在遍历的过程中这个区间的可行性却被反复检查了多次，造成了极大的浪费，这便是我们的优化点。

单调队列

有什么样的结构支持我们在已有的检查结果上更新，且这个检查明显和大小有关呢？答案已经写在标题里了，单调队列！

进一步思考一下我们的贪心思路，就$low, high$两个属性而言，$high$只是起到一个上限的作用，即判断这个序列可不可行；$low$是真正控制影响每一天的价格的主要因素，所以我们只考虑控制$low$的单调性。

我们知道，一个更大的$low$进队会提升当前的股票价格，这导致之前那个较小的$low$的控制失效，不再对以后的元素造成影响，可以排除出队列；而一个更小的$low$进队虽不会影响当前价格，但是可能在比它大的$low$出队后造成影响，所以应该予以保留。这样看的话，单调性也很明显了：我们要维护一个关于$low$递减的单调队列。我们将用这个队列来代表以当前队尾元素所属的那一天结尾的最长不降序列。

注意！这个队列只是「代表」该序列的一些性质，队首「不一定」是这个不降序列起始的那一天！

另外，关于这里的递减是否严格，就后面的算法来看似乎并没有什么影响，可以暂且忽略。

这里就很自然地引出了一个问题，如果队首元素不是起始的那一天，那怎么更新答案？那另外把起始点存下来不就好了！我们可以假设以第$i$天结尾的满足$low$单调递增的序列所对应的起始点为$start_i$，然后在维护队列的同时对其进行更新。

这里所谓以第$i$天结尾的$low$递增的序列就是那些在单调队列中会被出队，但是会「在$i$作为队首时」对答案有贡献的元素。

举例说明，如果一列$low$为$2, 1, 2, 3, 4, 2, 5$，那么每个位置对应的$start_i$即为$0,1,1,1,1,5,5$。如果某时刻$low_3=3$为单调队列的队首，那么真正的起始点就应该是$start_3=1$（$low_1=1,low_2=2$只是不满足单调队列的性质，但是是满足题目的不降的要求的）

由于要额外维护$start$，方便起见，我们在队列中储存$i$，而非$low_i$的值。具体来说，我们记队首元素为$l$，队尾元素为$r$，当一个$low_i$入队时，我们应该先检测当前的序列是否能够以第$i$天结尾，即$high_i$是否大于前面元素的$low$的最大值。由于队列是单调递减的，所以$low$的最大值就储存在队首，我们可以不断比较并出队，将比$high_i \ge low_l$为止，这样剩余处在队列中的元素即可满足以第$i$天结尾的条件。

然后对队列的单调性进行维护，将$low_i$和$low_r$进行比较，如果$low_i>low_r$，那么意味着只要到达第$r$天，就一定能到达第$i$天（即$low_i$的控制失效），于是令$start_i=start_r$，并将队尾元素出队。不断重复这个过程，直至$low_r\leq low_i$。然后将$i$入队。

关于这里令$start_i=start_r$的合理性，进一步说明如下：
首先有$high_i \geq low_l$（第一步检查），而队列又是关于$low$单调递减的，故一定有$high_i \geq low_l \geq low_r$。所以从第$r$天一定能到达第$i$天。

关于答案的更新，只要检查后用$i - start_l$更新最大值即可。

下面贴出代码：

代码仅供参考，请不要盲目抄袭代码来完成作业！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>

constexpr int MAXN = 1e6L + 10L;

int n;
int high[MAXN], low[MAXN], st[MAXN], q[MAXN];

int main() {
    scanf("%d", &n);
    int l = 0, r = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d%d", low + i, high + i);
        while (l <= r && low[q[l]] > high[i]) l++;
        st[i] = i;  // start默认位置是从自己开始
        while (l <= r && low[q[r]] < low[i]) st[i] = st[q[r--]];
        q[++r] = i;
        ans = std::max(i - st[q[l]], ans);
    }
    printf("%d", ans + 1);
    return 0;
}

一些改进

前文中写到，方便起见，所以在单调队列中储存了索引值（个人认为这样也比较好理解）。但是我们可以看到，这样做实际上空间复杂度是$O(4n)$。尽管通过本题绰绰有余，但是仍然有优化空间。

观察发现，无论是$low$还是$start$的调用频次实际上也仅仅是在进队和队首处，一旦出队就不会再进行访问。所以我们回到原始思路，在单调队列中就储存$low$的值，然后再开一个队列与之对应，存储对应位置元素$start$的值（也可以使用结构体）。这样空间复杂度就降低到了$O(2n)$，甚至连$low$和$high$都不需要另外完整地保存下来。

代码如下：

代码仅供参考，请不要盲目抄袭代码来完成作业！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>

constexpr int MAXN = 1e6L + 10L;

int n;
int st[MAXN], q[MAXN];

int main() {
    scanf("%d", &n);
    int l = 0, r = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        int low, high, rec = r;  // rec用来判断是否进行了队尾出队操作
        scanf("%d%d", &low, &high);
        while (l <= r && q[l] > high) l++;
        while (l <= r && q[r] < low) r--;
        if (rec == r) st[r + 1] = i;  // 没有更新就设定为默认值
                                      // 如果更新了就不用管，st[r+1]本来就存储着之前的值，可以直接使用
        q[++r] = low;
        ans = std::max(i - st[l], ans);
    }
    printf("%d", ans + 1);
    return 0;
}

受笔者知识水平和表达能力所限，有的问题难免解释得或啰嗦或不清楚，欢迎在评论区指正