Next larger number in an array

You are given an unsorted array A of n elements, now construct an array B for which B[i] = A[j] where j is the least number such that A[j] > A[i] and j>i if such a j does not exist B[i] = -1 Eg:

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

My solution

#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;
    retu开发者_如何学Gorn 0;
}

can any one suggest o(nlogn) solution.

---

I did it in 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);
    }
}

---

Make an empty array called c[].

Start at the end of a[] and work backwards.

Do a binary search in c[] for the first value greater than a[i]. Put that into b[i], or a -1 if you can't find one.

Drop everything in c[] that is less than b[i].

Append a[i] to the beginning of c[].

c[] will always be sorted, allowing binary search.

---

For example, with the sample A={1,3,5,7,6,4,8}

Start at the end, A[i]=8, C={}
First iteration is a bit weird.
Binary search of C for the first value greater than 8 gives nothing, so B[i] = -1
You don't have to drop anything from C because it is empty, but you would have had to empty it anyway because of the -1.
Append A[i]=8 to the beginning of C, so C={8}

Now A[i]=4, C={8}
Binary search of C for the first value greater than 4 gives 8, so B[i]=8
Drop everything less than 8 from C, which still leaves C={8}
Append A[i]=4 to the beginning of C, so C={4,8}

Now A[i]=6, C={4,8}
Binary search of C for the first value greater than 6 gives 8, so B[i]=8
Drop everything less than 8 from C, which leaves C={8}
Append A[i]=6 to the beginning of C, so C={6,8}

Now A[i]=7, C={6,8}
Binary search of C for the first value greater than 7 gives 8, so B[i]=8
Drop everything less than 8 from C, which leaves C={8}
Append A[i]=7 to the beginning of C, so C={7,8}

Now A[i]=5, C={7,8}
Binary search of C for the first value greater than 5 gives 7, so B[i]=7
Drop everything less than 7 from C, which leaves C={7,8}
Append A[i]=5 to the beginning of C, so C={5,7,8}

Now A[i]=3, C={5,7,8}
Binary search of C for the first value greater than 3 gives 5, so B[i]=5
Drop everything less than 5 from C, which leaves C={5,7,8}
Append A[i]=3 to the beginning of C, so C={3,5,7,8}

Now A[i]=1, C={3,5,7,8}
Binary search of C for the first value greater than 1 gives 3, so B[i]=3

Done

---

Binary search is a red herring here, I think. Despite nested loops, this performs only n item comparisons and n item copies.

int _tmain()
{
    int a[]=/*{1,3,5,7,6,4,8};*/{9,3,5,2,6,4,8};
    int b[_countof(a)];


    int prevIdx = 0;
    for(int i = 0; i < _countof(a); i++)
    {
        if(a[i] > a[prevIdx])
        {
            for(int j = prevIdx; j < i; j++)
                b[j] = a[i];

            prevIdx = i;
        }
    }

    for(int j = prevIdx; j < _countof(b); j++)
        b[j] = -1;

    for(int j=0;j<7;j++)
        std::cout<<b[j]<<std::endl;

    return 0;
}