下一个更大元素的时间复杂性

Question

我参考了GeeksforGeeks的this问题解决了Next Greater Element问题。我很困惑地发现以下问题的时间复杂度（Big O）。如果有人可以帮助我这将是非常有帮助的。

问题：给定一个数组，为每个元素打印Next Greater Element（NGE）。元素x的下一个更大元素是数组中x右侧的第一个更大元素。不存在更多元素的元素，将下一个更大元素视为-1。

例子：

a）对于任何数组，最右边的元素总是将下一个更大的元素作为-1。

b）对于按降序排序的数组，所有元素都有下一个更大的元素为-1。

How to find the time complexity of this?

这是解决这个问题的可接受方式吗？

    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

由于您使用的是continue，因此难以确定算法的复杂性，这会给您的推理带来不必要的困难。

重写以下内容（不使用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。