[USACO09MAR] Look Up S

题目解析

暴力解法

对于每头牛 i，我们都需要向右寻找第一个身高比它高的牛 j。最直接的方法是使用两层循环：

外层循环遍历每头牛 i (从 1 到 n)。
内层循环从 i+1 开始向右遍历，找到第一个身高 h[j] > h[i] 的牛 j，并记录其下标。

这种方法的时间复杂度为 $O(n^2)$ 。对于本题的数据范围， $n$ 最大可达 $10^5$ ， $O(n^2)$ 的算法无法通过所有测试点，只能得到部分分数。因此，我们需要更高效的算法。

单调栈优化

我的思路: 直觉: 二层暴力 $n^2$ , 得到50分

直接: $i,i+1$ 两个cow的备选空间大部分相同,看看是否有单调性.

和单调队列的思维方式一样:

对i的后选区间 $[i+1,n]$ ,进行刷选,去除不可能的值(被遮挡的值),

留下来的元素是单调的

证明: 留下来的元素是单调的,

$x, y \in [i+1,n]$

$h[y] < h[x] \to \text{y 不能对 [1,i] 中的所有的元素产生贡献}$

得到候选元素中不可能存在,一对元素 x < y \land h[y] < h[x]$

也就是: 任意两个元素: 总是前面小后面大

当 i 变到 i-1 时, 更新候选元素

观察暴力解法，我们会发现其中存在大量的重复计算。当我们为牛 i 寻找答案时，扫描了区间 [i+1, n]。当我们为牛 i-1 寻找答案时，我们又会扫描区间 [i, n]。这两个区间高度重合，这提示我们可以利用之前计算的信息来加速后续的查找。

这种 “寻找下一个更大/更小元素” 的问题是单调栈的典型应用场景。单调栈是一种特殊的栈，其内部元素始终保持单调性（单调递增或单调递减）。

在本题中，我们的目标是为每个元素 a[i] 找到右边第一个比它大的元素。为了方便处理，我们可以从右向左遍历数组。这样，当我们处理元素 a[i] 时，所有在 a[i] 右边的元素都已经处理过，并且相关信息可以存储在数据结构中。

我们维护一个单调栈，栈中存储牛的下标。这个栈从栈底到栈顶，对应牛的身高是单调递减的。

算法流程

我们从 i = n 遍历到 1：

维护单调性：对于当前牛 i，我们查看栈顶的牛 stk.top()。
- 如果栈不为空，且栈顶牛的身高 a[stk.top()] 小于或等于当前牛的身高 a[i]，说明栈顶的牛被当前牛 i "挡住"了。对于任何在 i 左边的牛来说，如果它们想找一个更高的牛，它们会先看到 i 而不是 stk.top()。因此，stk.top() 不可能成为 i 左边任何一头牛的答案，我们可以放心地将它弹出栈。
- 我们重复这个过程，直到栈为空或者栈顶的牛比当前牛 i 更高。
寻找答案：
- 经过上一步处理后，如果栈为空，说明在 i 的右边没有比它更高的牛了，所以牛 i 的答案是 0。
- 如果栈不为空，那么此时的栈顶元素 stk.top() 就是 i 右侧第一个比它高的牛的下标。
入栈：将当前牛 i 的下标压入栈中。这既是为了维持栈的单调性，也是为了让 i 成为后续（其左侧）牛的候选答案。

由于我们是从右向左遍历的，得到的答案序列是反的。因此，需要将最终结果反转后输出。

复杂度分析

时间复杂度：每个元素的下标最多被压入栈一次，也最多被弹出栈一次。因此，总的时间复杂度为 $O(n)$ 。
空间复杂度：在最坏的情况下（例如，所有牛的身高单调递减），所有牛的下标都会被压入栈中，所以空间复杂度为 $O(n)$ 。

代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2025-12-31 11:21:52
 */
#include <algorithm>
#include <bits/stdc++.h>
#include <stack>
#include <vector>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,m;
int a[maxn]; // 存储牛的高度


// 从后往前遍历，所以答案需要倒序存储
std::vector<int> ans;

// 单调栈，存储牛的下标
std::stack<int> stk;

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
    }

    // 从后往前遍历，寻找每个元素右边第一个比它大的元素
    for(int i = n;i >= 1;i--) {
        // std::cout << "deal " << a[i] <<   "\n";


        // 维护单调栈：当栈不为空，且栈顶牛的高度小于等于当前牛的高度时，
        // 说明栈顶的牛不可能成为在当前牛左边任何一头牛的答案（因为它更近且更矮，被当前牛挡住了），
        // 所以将其弹出。
        while( stk.empty() == false && a[stk.top()] <= a[i] )
            stk.pop();

        // 经过上面的循环，栈顶的元素（如果存在）就是i右边第一个比a[i]大的牛的下标
        if( stk.empty() ) 
            ans.push_back(0); // 如果栈为空，说明右边没有比它高的牛
        else
            ans.push_back(stk.top()); // 否则，栈顶就是答案

        // 将当前牛的下标压入栈中，作为后续（左边）牛的候选答案
        stk.push(i);
    }


    // 因为是倒序遍历得到的答案，所以需要反转
    std::reverse(ans.begin(),ans.end());
    for( auto u: ans) std::cout << u << "\n";
    
    return 0;
}

目录

题目解析

暴力解法

单调栈优化

算法流程

复杂度分析

代码