c++ - 数组中的下一个更大的数字

Question

给定一个包含 n 个元素的未排序数组 A，现在构造一个数组 B，其中B[i] = A[j] 其中 j 是满足 A[j] > A[i] 且 j>i 的最小数如果这样的 j 不存在 B[i] = -1例如:

A={1,3,5,7,6,4,8}
B = {3 5 7 8 8 8 -1}

我的解决方案

#include<iostream>
using namespace std;
int main()
{
    int a[7]={9,3,5,2,6,4,8},b[7];
    int i,j,largest = -1;
    for(i=0;i<7;i++)
    {
        j=i+1;
        while(j<7)
        {
         if(a[j]>a[i])
         {
             largest=a[j];
             break;
         }
         j++;
        }
        if(j == 7)
        largest = -1;
        b[i]= largest;
    }
    for(j=0;j<7;j++)
    cout<<b[j]<<endl;
    return 0;
}

谁能提出 o(nlogn) 解决方案。

Answer 1

我在 O(N) 中完成了

import java.util.Stack;

public class Test {

    public static void upateArray(int[] a){
        Stack<Integer> stack = new Stack<Integer>();
        int len = a.length;
        int cur = 0;
        while(cur < len){
            while(!stack.isEmpty() && a[stack.peek()] < a[cur]){
                a[stack.pop()] = a[cur];
            }
            stack.push(cur);
            cur++;
        }
    }

    public static void main (String args[]){
        int a[] = {3,2,5,11,4,11,13,8,6,20,10};
        upateArray(a);
        for(int i : a)
            System.out.print(" "+i);
    }
}