查找每個數組元素，左邊較小的元素。 O（n）

Question

有一個我一直在尋找的着名問題，它是： 在一個給定的數組上，我們試圖構建另一個相同大小的數組， ，新數組中的每個元素都是原始數組中左側的較小元素的數量（連續）。我一直在StackOverflow中尋找，我只在O（nlogn）中找到解決方案。我認爲我在O（n）找到了一個解決方案。

int[] arr = {8, 4, 3, 2, 10, 9, 7, 6, 12}; 
Stack<Integer> stack = new Stack<>(); 
int[] newArr = new int[arr.length]; 

// Each sequence is at least 1; 
for (int i = 0; i < newArr.length; i++) { 
    newArr[i] = 1; 
} 

// For each element, if it is smaller than 
// the previous one, push it into the stack. 
// Otherwise, compare it to all the elements 
// in the stack which are smaller or equals to it, 
// and summarize their values in the newArr. 
stack.push(arr[0]); 
for (int i = 1; i < arr.length; i++) { 
    if (arr[i] >= arr[i-1]) { 
     int j = i - 1; 
     while (!stack.isEmpty() && stack.top() <= arr[i]) { 
      arr[i] += newArr[j]; 
      stack.pop(); 
      j--; 
     } 
    } 
    stack.push(arr[i); 
} 

現在，複雜的時間，爲O（n），因爲任何值與只有一次， 並且在最壞的情況下，當有「N」標記，並且它們被分成 數k （例如{18,12,11,9,17，8，6，4，15，3，2，1}），我們 只激活第二個循環'k'次，對於'n/k'元素。這就是爲什麼 'k'變量不重要，在最壞的情況下我們留下了O（n）。

*我忘了提，即newArr中的代碼應該是這樣的： {1，1，1，1，5，1，1，1，9} *

讓我知道我是否正確，這對我來說非常重要。 此致， 烏利亞。

Answer 1

是的，你的論點絕對正確。你的代碼的時間複雜度是O（n）。

它也可以很容易地證明，每個數字都被添加並從棧中彈出一次。因此使它成爲O（n）。

---

替代算法來執行相同任務（很多更直觀）：

// push index instead of number itself 
stack.push(0); 
for (int i = 1; i < arr.length; i++) { 
    while (!stack.isEmpty() && arr[stack.top()] <= arr[i]) 
     stack.pop(); 
    if(stack.isEmpty()) 
     new_arr[i]=i+1; 
    else 
     new_arr[i]=i-stack.top() 
    stack.push(i); 
} 

正如你可以看到，我推指數，而不是數量。這使新陣列的計算變得直觀（只計算兩個索引之間的差異）。