n个整数的无序数组,输出每个元素后面比它大的第一个数的下标,要求时间复杂度为 O(n) C++代码实现

为了在一个无序整数数组中找到每个元素后面比它大的第一个数的下标，并保持时间复杂度为O(n)，你可以使用双指针策略。首先遍历数组，维护两个指针i（当前元素）和j（寻找大于当前元素的第一个位置）。当找到第一个大于i的元素，就记录下j的位置，然后将i向右移动一位。

以下是C++代码实现：

#include <vector>
using namespace std;

void findNextLarger(int arr[], int size) {
    vector<int> result(size, -1); // 初始化结果数组，值为-1表示未找到更大元素

    for (int i = 0; i < size; i++) {
        if (i == 0 || arr[i] > arr[i - 1]) { // 如果当前元素大于前一个或者是最左边的元素
            // 使用滑动窗口技巧找右边第一个大于arr[i]的元素
            for (int j = i + 1; j < size; j++) {
                if (arr[j] > arr[i]) {
                    result[i] = j;
                    break;
                }
            }
        }
    }

    // 输出结果
    for (int i = 0; i < size; i++) {
        if (result[i] != -1) {
            cout << "Element " << arr[i] << " has the next larger number at index " << result[i] << endl;
        } else {
            cout << "No such element found for " << arr[i] << endl;
        }
    }
}

int main() {
    int arr[] = {4, 1, 3, 6, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    findNextLarger(arr, size);
    return 0;
}

当你运行这段代码时，它会输出每个元素后面比它大的第一个数的下标（如果存在），否则输出“没有找到更大的元素”。