java - 下一个更大元素的时间复杂度

Question

我已经引用 this 解决了下一个更大元素问题来自 GeeksforGeeks 的问题。我很困惑找到以下问题的时间复杂度(大O)。如果有人能在这方面帮助我，那将非常有帮助。

问题:给定一个数组，打印每个元素的下一个更大元素 (NGE)。元素 x 的下一个更大元素是数组中 x 右侧的第一个更大元素。不存在更大元素的元素，将下一个更大元素视为-1。

示例:

a) 对于任何数组，最右边的元素始终具有下一个更大的元素 -1。

b) 对于按降序排序的数组，所有元素的下一个较大元素均为 -1。

1. 如何求这个的时间复杂度？

2. 这是解决此问题的可接受方法吗？

       int[] array = {20,10,5,3};
   
       int len =array.length;
       int[] temp = new int[len];
   
       int j=0;
       int i=j;
       while(j<len-1){
           ++i;
           if(i>=len){
               System.out.println(array[j]+"----> -1");
               j++; i=j;
               continue;
           }
           if(array[j]<array[i]){
               System.out.println(array[j]+"----> "+array[i]);
               j++; i=j;
           }
       }
       System.out.println(array[j]+"----> -1");
   

Answer 1

您很难决定算法的复杂性，因为您使用的是继续，这给您的推理增加了不必要的困难。

重写为以下内容(不使用 break 或 continue):

public void test() {
    int[] array = {10, 20, 3, 5};

    int len = array.length;

    for (int j = 0; j < len - 1; j++) {
        int nge = -1;
        for (int i = j + 1; i < len && nge < 0; i++) {
            if (array[j] < array[i]) {
                nge = array[i];
            }
        }
        System.out.println(array[j] + "----> " + nge);
    }
    System.out.println(array[len-1] + "----> -1");
}

现在很清楚，这是 O(n lg n)，因为外部循环迭代到 n，内部循环迭代到 n - j.