题目链接

我在仰望~

题目描述

有 只奶牛站成一排，第 只奶牛的身高是 。

每只奶牛都在向右看。对于奶牛 ，如果存在一只奶牛 满足 且 ，则称奶牛 可以仰望奶牛 。

需要求出每只奶牛 右侧第一个身高比它高的奶牛 的编号。如果不存在这样的奶牛，则输出 。

解题思路

本题的实质是求解每个元素的“下一个更大元素”（Next Greater Element）。对于数组中的每个元素，我们需要找到它右边第一个比它大的元素。

一个朴素的解法是使用双重循环：对于每个奶牛 ，向右遍历直到找到第一个身高 的奶牛 。这种方法的时间复杂度为 ，在 较大时会超时，因此需要更高效的算法。

这个问题可以使用单调栈在 的时间内解决。单调栈是一种特殊的栈，它在任何时候都保持栈内元素的单调性（单调递增或单调递减）。

我们可以从右向左遍历所有奶牛（从 到 ）。在遍历过程中，我们维护一个单调栈，该栈从栈底到栈顶，存储的奶牛身高是单调递减的。实际上，我们只需在栈中存储奶牛的编号。

算法流程：

  1. 初始化一个空栈 st 用于存储奶牛编号，以及一个结果数组 ans。

  2. 从右向左遍历奶牛，即 从 递减到 ：
    a. 当栈不为空，且栈顶奶牛的身高小于或等于当前奶牛 的身高时（h[st.top()] <= h[i]），说明栈顶的奶牛对于左边的任何奶牛来说，都不会是第一个更高的奶牛（因为它被奶牛 “挡住”了）。因此，将这些奶牛的编号从栈中弹出。
    b. 经过上一步的弹出操作后：
    - 如果栈为空，说明在奶牛 的右侧不存在比它更高的奶牛。因此，奶牛 的仰望对象为 。
    - 如果栈不为空，那么此时的栈顶元素就是奶牛 右侧第一个比它高的奶牛。记录其编号。
    c. 将当前奶牛 的编号压入栈中。这维持了栈的单调性，因为所有比 矮的、在 右侧的奶牛都已经被弹出了。

  3. 遍历结束后，输出结果数组 ans。

通过这种方式，每个奶牛的编号最多被压入和弹出栈一次，总时间复杂度为 。

代码

#include <iostream>
#include <vector>
#include <stack>

int main() {
    using namespace std;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> h(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> h[i];
    }

    vector<int> ans(n + 1);
    stack<int> st;

    for (int i = n; i >= 1; --i) {
        while (!st.empty() && h[st.top()] <= h[i]) {
            st.pop();
        }
        if (st.empty()) {
            ans[i] = 0;
        } else {
            ans[i] = st.top();
        }
        st.push(i);
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] h = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            h[i] = sc.nextInt();
        }

        int[] ans = new int[n + 1];
        Stack<Integer> st = new Stack<>();

        for (int i = n; i >= 1; i--) {
            while (!st.isEmpty() && h[st.peek()] <= h[i]) {
                st.pop();
            }
            if (st.isEmpty()) {
                ans[i] = 0;
            } else {
                ans[i] = st.peek();
            }
            st.push(i);
        }

        for (int i = 1; i <= n; i++) {
            System.out.println(ans[i]);
        }
    }
}

import sys

def main():
    n_str = sys.stdin.readline()
    if not n_str.strip():
        return
    n = int(n_str)
    
    # 读取剩余的所有输入，按空白符分割，然后转换为整数列表
    # 这种方法可以稳健地处理数字分布在多行的情况
    h = list(map(int, sys.stdin.read().split()))

    ans = [0] * n
    st = []  # 栈中存储 0-based 索引

    # 从右向左遍历
    for i in range(n - 1, -1, -1):
        while st and h[st[-1]] <= h[i]:
            st.pop()
        
        if not st:
            ans[i] = 0
        else:
            # 结果需要 1-based 索引
            ans[i] = st[-1] + 1
        
        st.append(i)

    for i in range(n):
        print(ans[i])

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法: 单调栈
  • 时间复杂度: ，因为每个奶牛的编号最多入栈和出栈一次。
  • 空间复杂度: ，用于存储单调栈和结果数组。在最坏情况下（例如身高严格递减的序列），所有奶牛的编号都会被压入栈中。