奶牛排队

GitHub跳转原题关系图返回列表

固定右端 r,合法左端只能是左侧最后一个身高不低于 a[r] 的位置之后的最小值,用两个单调栈加一次二分做到 O(n log n)。

OJ: roj

题目 ID: 1747

难度:提高

标签:单调栈数据结构二分python

创建: 2026-10-07 21:08

更新: 2026-10-07 21:08

形式化题目

给定长度为 nn 的身高序列 a1,a2,…,ana_1, a_2, \dots, a_n(2⩽n⩽1052 \leqslant n \leqslant 10^5,1⩽ai⩽232−11 \leqslant a_i \leqslant 2^{32}-1), 求最长的区间 [l,r][l, r](l<rl < r),满足

al<ak(l<k⩽r),ar>ak(l⩽k<r). a_l < a_k \quad (l < k \leqslant r), \qquad a_r > a_k \quad (l \leqslant k < r).

第一条说 ala_l 是区间内的严格最小值,第二条说 ara_r 是区间内的严格最大值。 两条合起来自动蕴含 al<ara_l < a_r(取 k=rk = r 即得),也正是题面里 "BB 高于 AA、中间的身高不能和 AA 或 BB 相同"三句话的合写: 中间的身高既不小于 AA 又不等于 AA,只能严格大于 AA;对 BB 同理。

若不存在这样的区间则输出 00。因为长度 11 的区间只有一个端点、谈不上"最矮且最高", 答案只能是 00 或 ⩾2\geqslant 2。

正解

思路

朴素做法。 枚举所有 O(n2)O(n^2) 个区间,每个区间扫一遍检查两条不等式, 总复杂度 O(n3)O(n^3);n=105n = 10^5 时不可行。瓶颈很清楚:区间是二维的, 而"最小/最大"这种约束天然可以从固定一端开始消掉一个维度。

固定右端 rr。 此时第二条不等式 ar>ak  (l⩽k<r)a_r > a_k\;(l \leqslant k < r) 只和 ll 有关, 把它改写成"左边哪些下标不能当 ll":

p(r)=max⁡{ k<r:ak⩾ar }(不存在时记 0), p(r) = \max\{\,k < r : a_k \geqslant a_r\,\} \quad(\text{不存在时记 } 0),

那么 ara_r 是 [l,r][l, r] 内严格最大值 当且仅当 l>p(r)l > p(r)—— 因为 p(r)p(r) 右边(不含 p(r)p(r) 本身)到 r−1r-1 的所有身高都 <ar< a_r。

再看第一条。 定义 q(l)=min⁡{k>l:ak⩽al}q(l) = \min\{k > l : a_k \leqslant a_l\}(不存在记 +∞+\infty), 即 ala_l 右方第一个不高于它的位置。第一条不等式等价于 r<q(l)r < q(l): 在 ll 右边直到 rr 的所有身高都 >al> a_l。

于是问题变成:固定 rr,求最小的 ll 使得 l>p(r)l > p(r) 且 q(l)>rq(l) > r。 (ll 越小,区间 r−l+1r - l + 1 越长。)

关键观察:满足 q(l)>rq(l) > r 的 ll 构成一个单调栈。 维护一个身高严格递增的栈 SS, 遇到 ara_r 就把栈里所有 ⩾ar\geqslant a_r 的下标弹掉,再压入 rr。按 rr 从小到大归纳可得

Sr={ l⩽r:q(l)>r }, S_r = \{\,l \leqslant r : q(l) > r\,\},

且 SrS_r 中的下标随栈深递增、身高也随栈深递增。两边的方向是反的: 弹栈条件是"身高 ⩾ar\geqslant a_r",弹掉的正是不再满足 q(l)>rq(l) > r 的下标; 而留下的下标都满足 al<ara_l < a_r,即 q(l)>rq(l) > r。

二分求最优左端。 SrS_r 的下标递增,所以"SrS_r 中第一个 >p(r)> p(r) 的下标" 用一次 upper_bound 就能取到,它就是 rr 对应的最优左端 l∗l^*:

  • 因为 l∗>p(r)l^* > p(r),ara_r 是 [l∗,r][l^*, r] 的严格最大值;
  • 因为 l∗∈Srl^* \in S_r,al∗a_{l^*} 是 [l∗,r][l^*, r] 的严格最小值;
  • 任何 l<l∗l < l^* 的候选要么 ⩽p(r)\leqslant p(r)(破坏第二条),要么 ∉Sr\notin S_r(破坏第一条)。

枚举所有 rr 取最大值即可。p(r)p(r) 同样用一个身高非增的栈 DD 维护: 遇到 ara_r 弹掉所有 <ar< a_r 的下标,此时栈顶就是左边最后一个 ⩾ar\geqslant a_r 的位置。

样例走一遍。 a=(1,2,3,4,1)a = (1, 2, 3, 4, 1)(下标从 1 开始):

rr ara_r p(r)p(r) SrS_r(下标) l∗l^* 区间长度
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(不合法)

r=4r = 4 时 l∗=1l^* = 1,区间 [1,4][1, 4] 就是样例答案 44;r=5r = 5 时 p(5)=4p(5) = 4(a4=4⩾a5=1a_4 = 4 \geqslant a_5 = 1),S5={5}S_5 = \{5\},找不到 l<5l < 5, 所以最后一头牛无法延长任何区间。

为什么不能只用一个栈? 两个栈的弹栈条件不同(DD 弹 <ar< a_r、SS 弹 ⩾ar\geqslant a_r), 处理的是两件相反的事:DD 找"左边最后一个挡住 ara_r 的大个子", SS 维护"右边界还能延伸的左端集合"。SS 的下标单调性让二分成立, 而 SS 的身高单调性保证了"SS 中 ⩾\geqslant 某值的位置"可以靠下标定位。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

  • 时间:每个下标最多被 DD、SS 各压入弹出一次,弹栈总代价 O(n)O(n); 每个 rr 额外做一次 upper_bound,共 O(nlog⁡n)O(n \log n)。 n=105n = 10^5 时实际运算量约 nlog⁡2n≈1.7×106n \log_2 n \approx 1.7 \times 10^6 次比较, C++ 实测 0.010.01 s 量级(含进程启动,限时 1000 ms)。
  • 空间:两个栈各 O(n)O(n),加上原数组,总空间 O(n)O(n); check_sample.py 实测 C++ 峰值内存 8.38.3 MB,Python 峰值约 1818 MB (限时 128 MB)。
  • 值域:身高上限 232−12^{32}-1 超出 int,C++ 侧必须用 long long 读入, Python 侧原生大整数不需要处理。
  • 与 C++ 解法的关系:main.py 与 main.cpp 是同一算法的两个语言版本, 都用"两个单调栈 + 一次二分",复杂度同为 O(nlog⁡n)O(n \log n)。 Python 用 bisect_right 代替手写二分,常数更小;n=105n = 10^5 实测 0.050.05 s, 不存在本题特有的 TLE 风险。

总结

  • 固定一端消掉一个维度:区间问题先想"枚举 rr,ll 的最优值能不能 O(log⁡n)O(\log n) 求出来"。
  • "严格最值"翻译成位置条件:ara_r 是 [l,r][l, r] 的最大值   ⟺  l>p(r)\iff l > p(r); ala_l 是 [l,r][l, r] 的最小值   ⟺  r<q(l)\iff r < q(l)。两条不等式各自退化成一个下标阈值。
  • 单调栈存的是"可行集合":Sr={l⩽r:q(l)>r}S_r = \{l \leqslant r : q(l) > r\} 这个集合恰好是 一个身高严格递增的栈,下标递增让"第一个 >p(r)> p(r) 的元素"能用二分取出。
  • 相等元素必须按题面处理:弹栈条件是 ⩾ar\geqslant a_r(不是 >ar> a_r), 这样相等的身高会互相排斥,符合"中间不能和 AA、BB 相同"的要求; 写成严格不等号会把全相等的序列误判成有解。
  • 答案可能是 00(例如 a=(2,1)a = (2, 1) 或全相等),也可能是 nn(严格递增), 长度 11 的区间要显式排除。
  • 素材与数据说明(如实注明):题面与数据取自仓库内 new_ROJ/problems/1747/ (题面标注来源"信息学奥赛一本通 · 高手训练篇 · 数据结构",判题 OJ 为 roj.ac.cn), 素材目录带有数据生成脚本 data.py,说明 data/ 是按题面自造的, 出题意图与官方原题可能存在偏差;素材自带的 std.cpp 与本解法思路一致 (同为"两个单调栈 + 二分"),已编译并在 10 个测试点上逐点比对,答案全部一致。

图示解析

下图重演样例 a=(1,2,3,4,1)a = (1,2,3,4,1) 在 r=4r = 4 与 r=5r = 5 两个时刻的两个栈。 DD 是身高非增栈,栈顶给出 p(r)p(r);SS 是身高严格增栈,栈内都是"右边界还能延伸到 rr 的合法左端"。

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

读图要点有三处。第一,两个栈的弹栈条件相反:DD 弹"身高更矮的", 所以它总能留住左边最大的那个"拦路者";SS 弹"身高不更矮的", 所以它留下的下标身高严格递增,且 ala_l 是 (l,r](l, r] 上的最小值。 第二,r=5r = 5 时 SS 被清到只剩自己,说明身高 11 既压不住前面任何一头牛 (不满足"左端最矮"),又会被前面最高的 44 挡住(不满足"右端最高"), 所以最后一头牛对答案零贡献。第三,每个下标在 DD、SS 里各进出一次, 这就是总复杂度 O(nlog⁡n)O(n \log n) 里那个 O(n)O(n) 的来源,log⁡\log 只来自每轮的二分。