思路
大牛一眼看出滑动窗口,这里给出详细解释(本人纯蒟蒻)大牛可以走了。
解法1(暴力)
纯暴力理论 40pts, 实际得分 70pts, @xw_qwq 大佬使用暴力加优化拿了 100pts。
解法2(滑动窗口)
Q:为什么要用滑动窗口?
显然的,我们的温度区域是一个线性结构,为了保证我们选出的最长上升序列是最优的,我们可以考虑维护一个双端队列, 在时间复杂度 O(n) 的时间内得出一个最好的选择。
Q:如何维护这个滑动窗口?
首先,> b_i 的肯定不可以选择了,需要把他们踢出队列,然后 < a_i 的也需要被踢出,因为如果继续延续的话后面全部会变成 a_i,显然我们需要踢出去。
具体的说:先从队列前端移除所有L > b[i]的区间,因为这些区间的最小温度大于当前天的最大可能温度,无法与当前天组成不下降序列,如果队列不为空,计算当前天到队列前端区间起始索引的长度,更新最大长度,然后从队列后端移除所有L <= a[i]的区间,因为当前天的最小温度a[i]更大,能形成更优的下界,合并这些区间并记录起始索引,最后将当前天形成的新区间加入队列后端。
这么说的话,这个代码实际上已经很好写了,我们给出核心 code
while (!qu.empty() && qu.front().L > b[i])
{
qu.pop_front();
}
if (!qu.empty())
ans = max(ans, i - qu.front().L + 1);
while (!qu.empty() && qu.back().L <= a[i])
{
tmp = qu.back().idx;
qu.pop_back();
}
qu.push_back({a[i], b[i], tmp});