固定右端 r,合法左端只能是左侧最后一个身高不低于 a[r] 的位置之后的最小值,用两个单调栈加一次二分做到 O(n log n)。
OJ: roj
题目 ID: 1747
难度:提高
标签:单调栈数据结构二分python
创建: 2026-10-07 21:08
更新: 2026-10-07 21:08
形式化题目
给定长度为
第一条说
若不存在这样的区间则输出
正解
思路
朴素做法。 枚举所有
固定右端
那么
再看第一条。 定义
于是问题变成:固定
关键观察:满足
且
二分求最优左端。 upper_bound 就能取到,它就是
- 因为
, 是 的严格最大值; - 因为
, 是 的严格最小值; - 任何
的候选要么 (破坏第二条),要么 (破坏第一条)。
枚举所有
样例走一遍。
| 区间长度 | |||||
|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | — | 1(长度 1,不合法) |
| 2 | 2 | 0 | 1, 2 | 1 | 2 |
| 3 | 3 | 0 | 1, 2, 3 | 1 | 3 |
| 4 | 4 | 0 | 1, 2, 3, 4 | 1 | 4 |
| 5 | 1 | 4 | 5 | — | 1(不合法) |
为什么不能只用一个栈? 两个栈的弹栈条件不同(
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 21:02
# update_at: 2026-10-07 21:08
import sys
from bisect import bisect_right
NONE = -1 # "不存在的位置":下标从 0 起,-1 比任何真实下标都小,可参与 bisect 的整数比较
def longest_run(a: list[int]) -> int:
"""返回满足"左端严格最小、右端严格最大"的最长区间长度,无解返回 0。
st_ge 是身高非增的单调栈,栈顶即"左边最后一个身高 >= a[r] 的位置"p(r);
st_lt 是身高严格增的单调栈,栈内恰好是"右边界能一直延伸到 r 的所有合法左端",
且下标随栈深递增。下标 > p(r) 的最小者既满足 a[l] < a[r]、又满足 a[l] 是 (l, r]
上的最小值,所以它就是右端固定为 r 时的最优左端。
"""
st_ge: list[int] = [] # 存下标,身高随栈深非增
st_lt: list[int] = [] # 存下标,身高随栈深严格增
ans = 0
for r, value in enumerate(a):
while st_ge and a[st_ge[-1]] < value:
st_ge.pop() # 身高更矮的挡不住 value,后面再也用不上
p = st_ge[-1] if st_ge else NONE
st_ge.append(r)
while st_lt and a[st_lt[-1]] >= value:
st_lt.pop() # 这些左端的右边界到不了 r,区间不可能延长到 r
st_lt.append(r)
pos = bisect_right(st_lt, p) # st_lt 里第一个下标 > p 的位置
left = st_lt[pos] if pos < len(st_lt) else r # 没有就退化成 l = r,长度 1 不合法
if left < r:
ans = max(ans, r - left + 1)
return ans
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
a = [next(data) for _ in range(n)]
print(longest_run(a))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 21:02
* update_at: 2026-10-07 21:08
*/
// main.cpp:奶牛排队。求最长的区间 [l, r],使 a[l] 是区间内严格最小、a[r] 是区间内严格最大。
// 两个单调栈 + 一次二分:st_ge 求"左边最后一个 >= a[r] 的位置"p(r),
// st_lt 恰好是"右边界能一直延伸到 r 的所有合法左端",其中下标 > p(r) 的最小者就是 r 的最优左端。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 100005; // n <= 1e5,留一点余量
ll a[MAXN]; // 奶牛身高,值域到 2^32-1,必须用 ll 承载
ll st_ge[MAXN]; // 身高非增的单调栈:栈顶是左边最后一个 >= a[r] 的下标,即 p(r)
ll st_lt[MAXN]; // 身高严格增的单调栈:栈内恰为 { l <= r : a[l] < min(a[l+1..r]) }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
for (ll i = 1; i <= n; i++) cin >> a[i];
ll top_ge = 0; // st_ge 的栈顶指针
ll top_lt = 0; // st_lt 的栈顶指针
ll ans = 0;
for (ll r = 1; r <= n; r++) {
// 求 p(r):左边最后一个身高 >= a[r] 的位置。它右侧到 r-1 的所有身高都 < a[r],
// 所以只要左端 l > p(r),a[r] 就是 [l, r] 上的严格最大值。
while (top_ge > 0 && a[st_ge[top_ge]] < a[r]) top_ge--;
ll p = (top_ge > 0) ? st_ge[top_ge] : 0; // 0 表示左边不存在这样的位置
st_ge[++top_ge] = r;
// 维护 st_lt:弹掉所有身高 >= a[r] 的左端(它们的右边界延伸不到 r),
// 留下的每个 l 都满足 a[l] < a[r] 且 a[l] 是 (l, r] 上的最小值。
while (top_lt > 0 && a[st_lt[top_lt]] >= a[r]) top_lt--;
st_lt[++top_lt] = r;
// st_lt 的下标随栈深递增,二分出第一个下标 > p 的位置:
// 它同时满足 a[l] < a[r] 与 a[l] < min(a[l+1..r]),下标又最小,所以区间最长。
ll lo = 1;
ll hi = top_lt;
ll pos = top_lt + 1; // 找不到时留在栈外
while (lo <= hi) {
ll mid = (lo + hi) / 2;
if (st_lt[mid] > p) {
pos = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
// 只有 l < r 才算真正的区间;pos 落在 r 自己身上时长度为 1,题面不允许,跳过。
if (pos <= top_lt && st_lt[pos] < r) {
ll len = r - st_lt[pos] + 1;
if (len > ans) ans = len;
}
}
cout << ans << '\n';
return 0;
}复杂度
- 时间:每个下标最多被
、 各压入弹出一次,弹栈总代价 ; 每个 额外做一次 upper_bound,共。 时实际运算量约 次比较, C++ 实测 s 量级(含进程启动,限时 1000 ms)。 - 空间:两个栈各
,加上原数组,总空间 ; check_sample.py实测 C++ 峰值内存MB,Python 峰值约 MB (限时 128 MB)。 - 值域:身高上限
超出 int,C++ 侧必须用long long读入, Python 侧原生大整数不需要处理。 - 与 C++ 解法的关系:
main.py与main.cpp是同一算法的两个语言版本, 都用"两个单调栈 + 一次二分",复杂度同为。 Python 用 bisect_right代替手写二分,常数更小;实测 s, 不存在本题特有的 TLE 风险。
总结
- 固定一端消掉一个维度:区间问题先想"枚举
, 的最优值能不能 求出来"。 - "严格最值"翻译成位置条件:
是 的最大值 ; 是 的最小值 。两条不等式各自退化成一个下标阈值。 - 单调栈存的是"可行集合":
这个集合恰好是 一个身高严格递增的栈,下标递增让"第一个 的元素"能用二分取出。 - 相等元素必须按题面处理:弹栈条件是
(不是 ), 这样相等的身高会互相排斥,符合"中间不能和 、 相同"的要求; 写成严格不等号会把全相等的序列误判成有解。 - 答案可能是
(例如 或全相等),也可能是 (严格递增), 长度 的区间要显式排除。 - 素材与数据说明(如实注明):题面与数据取自仓库内
new_ROJ/problems/1747/(题面标注来源"信息学奥赛一本通 · 高手训练篇 · 数据结构",判题 OJ 为 roj.ac.cn), 素材目录带有数据生成脚本data.py,说明data/是按题面自造的, 出题意图与官方原题可能存在偏差;素材自带的std.cpp与本解法思路一致 (同为"两个单调栈 + 二分"),已编译并在 10 个测试点上逐点比对,答案全部一致。
图示解析
下图重演样例
flowchart LR
subgraph R4["r = 4,a₄ = 4:p(4) = 0"]
D4["D: 1 2 3 4(身高 1 2 3 4)"] --> P4["p = 0,即左端不受限"]
S4["S: 1 2 3 4(下标与身高都递增)"] --> L4["第一个下标 > 0 的是 1 → l* = 1"]
L4 --> A4["区间 [1,4],长度 4"]
end
subgraph R5["r = 5,a₅ = 1"]
D5["D: 弹掉身高 < 1 的?没有,栈保持 1 2 3 4"] --> P5["栈顶 4 的身高 4 ≥ 1 → p(5) = 4"]
S5["S: 弹掉所有身高 ≥ 1 的下标 1..4"] --> S5b["只剩 5"]
S5b --> L5["S 里没有下标 > 4 且 < 5 的元素 → 本轮无合法区间"]
end
A4 -.-> P5
读图要点有三处。第一,两个栈的弹栈条件相反: