An unordered array of N integers. Find the first number after each element that is larger than it. The time complexity is O (n)

Get the title first , It's easy to think about each element , Traversing the elements behind it, you can find the first one larger than it , But in this case, the time consumption may exceed O（n）, Therefore, a lot of information may be missed , So that we have to compare every time , What should I use ？

Let's imagine , If my current processing object is the first element , If the second element is smaller than me , So what I need to do now is not to compare the relationship between the third element and the first element , Instead, the object being processed becomes the second element . If the third element is larger than the second , I'm going back to the first element , Does this save a lot of time ？

So we need a container to store unprocessed elements , You can know , Elements are last in, first out , Like the second element , The latter cut gets the result first , So we can use the stack （stack） To store unprocessed elements .

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
import java.util.Stack;

public class Test {

    public static void main(String[] args) {
        //int[] a = {2,1,3,2,5};
        int[] a = {2,1,3,5,2};
        int[] ints = demoStack(a);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i]+" ");
        }

    }
 public static int[] demoStack(int[] num){
        int len=num.length;
        if(len==0) return null;    // An empty array , Returns an empty 
        int[] result = new int[len];    // Return results ： initialization -1, Means not found 
        Stack<Integer> notFind = new Stack<>(); // Stack ：num No eligible element index found in 

        int i=0;
        while(i<len)    // Traversal array 
        {
            // If the stack is empty or currently num The element is not larger than the top of the stack , Stack the current element , Index back 
            if(notFind.empty() || num[notFind.peek()]>=num[i])
            {
                notFind.push(i++);
            }
            // Elements to be processed , And num The current element is larger than the stack top index element , eligible , Update the value of the index in the result array , The top of the stack .
            else
            {
                result[notFind.peek()]=num[i];
                notFind.pop();
            }
        }
        while (!notFind.empty()){
            result[notFind.peek()]=-1;
            notFind.pop();
        }
        return result;
    }
    }