有没有办法从直觉或证明中理解为什么以下的时间复杂度是 O(N)？
它的作用基本上是给定一个整数的输入，我们在进行反向扫描array时创建firstSmallLeft相同长度的数组 where firstSmallLeft[i]= 第一个索引 where array[index]< 。（即，对于索引 i，它从 i-1, ... , j 扫描，直到找到第一个较小的元素，使得 array[j] < array[i]）array[i]
例如，如果输入 = [3,2,5,6,4,1].
firstSmallLeft 会是[-1,-1,1,2,1,-1]
//input int[] array
int[] firstSmallLeft = new int[array.length];
firstSmallLeft[0] = -1;
for(int i = 1; i < array.length; i ++){
int cur = i -1;
while (cur >=0 && array[cur] >= array[i]){
cur = firstSmallLeft[cur];
}
firstSmallLeft[i] = cur;
}