C++ 算法题解：求数列中每个元素右边第一个比它大的数的下标

题目描述

给出一个数列 A，求出一个数列 B。其中 Bi 表示数列 A 中 Ai 右边第一个比 Ai 大的数的下标（从 1 开始计数），没有找到这一个下标 Bi 就为 0。输出数列 B。

输入描述:

第一行 1 个数字 n (n ≤ 10000) 第二行 n 个数字，第 i 个数字为 Ai (0 ≤ Ai ≤ 1000000000)

输出描述:

一共一行，第 i 个数和第 i+1 个数中间用空格隔开。

解题思路

根据题目描述，我们需要找到数列 A 中每个元素右边第一个比它大的数的下标，并输出数列 B。

我们可以使用一个栈来保存元素的下标，同时遍历数列 A。当遇到一个比栈顶元素大的元素时，我们就找到了栈顶元素的下一个更大元素，将其下标记录在数列 B 中，并将栈顶元素出栈。最后，返回数列 B。

C++ 代码实现

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

using namespace std;

vector<int> findNextGreaterIndex(const vector<int>& A) {
    int n = A.size();
    vector<int> B(n, 0);
    stack<int> st;
    
    for (int i = 0; i < n; i++) {
        while (!st.empty() && A[i] > A[st.top()]) {
            B[st.top()] = i + 1;
            st.pop();
        }
        st.push(i);
    }
    
    return B;
}

int main() {
    int n;
    cin >> n;
    
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    
    vector<int> B = findNextGreaterIndex(A);
    
    for (int i = 0; i < n; i++) {
        cout << B[i] << " ";
    }
    cout << endl;
    
    return 0;
}

代码解释

定义一个辅助函数 findNextGreaterIndex，传入数列 A，返回数列 B。
初始化一个大小为 n 的向量 B，并将所有元素初始化为 0。
初始化一个栈 st，用于保存元素的下标。
遍历数列 A，对于每个元素 Ai：
- 如果栈不为空且 Ai 比栈顶元素大，则找到栈顶元素的下一个更大元素，并将下标记录在 B 中，并将栈顶元素出栈。
- 将 Ai 的下标 i 压入栈中。
返回数列 B。

测试链接

你可以点击链接进行测试：牛客网 1007 题

总结

本题使用栈的特性，可以有效地找到每个元素右边第一个比它大的数的下标。希望本题解对您理解算法和解决类似问题有所帮助！