各配列要素、左の小さな要素を検索します。 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); 
} 

任意の値は、一度だけ比較 、そこ「n」は数字であり、そしてそれらは 「k個に分割され、最悪の場合、であるため、複雑時間は、O（N）であります（例：{18,12,11,9,17,8,6,4,15,3,2,1}）、私たちは であり、2回目のループを 'k'回だけ活性化し、 'n/k '個の要素を含む。そのため、 の 'k'変数は重要ではなく、最悪の場合はO（n）が残っています。

*私はコード内のnewArrは次のようになりますことを、言及を忘れてしまった： {1、1、1、1、5、1、1、1、9} *

は私をしてみましょう私が正しいかどうかを知って、それは私のために本当に重要です。 よろしくお願いいたします。 ウリア。

Answer 1

はい、絶対にあなたの議論の通りです。あなたのコードの時間複雑さはO（n）です。

また、各数値が追加され、正確に1回スタックからポップされるということも容易に証明できます。したがってそれを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); 
} 

：

---

代替アルゴリズムは、（多くの直感的な）同じタスクを実行します。これにより、新しい配列の計算が直感的になります（2つのインデックスの差を計算するだけです）。