題目：

官網題目連結

根據題目敘述，會給一個由 N 個整數組成的陣列 A 以及一個整數 M，你必須照順序遍歷 A 並執行以下判斷，之後返回結果陣列 R (包含 M 個整數) :

  • 當遍歷到 A[K]=X，且 1 ≤ X ≤ N 時，結果陣列 R[K-1] 的值要加 1。
  • 當遍歷到的 A[K]=N+1，則 R 中所有元素值都必須統一成當前 R 的最大元素值。

例如輸入 A=[3, 4, 4, 6, 1, 4, 4]，M=5 :

  1. 當 K=0，A[K]=3，R[3-1] 要加 1，R 就變成 [0, 0, 1, 0, 0]
  2. 當 K=1，A[K]=4，R[4-1] 要加 1，R 就變成 [0, 0, 1, 1, 0]
  3. 當 K=2，A[K]=4，R[4-1] 要加 1，R 就變成 [0, 0, 1, 2, 0]
  4. 當 K=3，A[K]=6，R[6-1] 等於 M+1，R 所有元素要等於當前最大元素 2，所以 R 就變成 [2, 2, 2, 2, 2]
  5. 當 K=4，A[K]=1，R[1-1] 要加 1，R 就變成 [3, 2, 2, 2, 2]
  6. 當 K=5，A[K]=4，R[4-1] 要加 1，R 就變成 [3, 2, 2, 3, 2]
  7. 當 K=6，A[K]=4，R[4-1] 要加 1，R 就變成 [3, 2, 2, 4, 2]，因為遍歷完了，所以 R 已是答案。

其實題目沒有要你遍歷，只是講計數規則，但這題不遍歷不能解，我覺得這樣寫題目說明應該比較好懂，如果你有想到不遍歷的方法歡迎在下方留言討論。

  • N 和 M 都是範圍 [1~100000] 的整數。
  • 陣列 A 裡的元素都是範圍 [1~N+1] 的整數。

解法：

最棘手的部分就在於「當 A[K]=N+1，R 中所有元素值都必須統一成當前 R 的最大元素值」，因為如果你要將 R 所有數字都即時更新成最大值的話，你的時間複雜度就會變成 O(N*M)，而這顯然不是最好的答案。

那麼如果我不要即時統一，而是只紀錄這個觸發要統一的事實，並在之後的點替換成最大值呢 ?
感覺是可行的方向，但要如何實現需要思考一下，我們會發現當你觸發統一時，假設當前 R 最大元素是 3，代表之後如果遇到小於 3 的元素就是尚未統一過的元素，而如果之後又觸發統一，且當前 R 最大元素變成 5，那麼之後遇到小於 5 的元素就是尚未統一過的元素，我們並不需要擔心他到底有沒有統一成 3 過了，因為反正他都比 5 小，我們不需要記錄他的所有歷程。

具體來說我們除了需要紀錄 R 的最大元素值 max 之外，還需要知道要統一的目標數字是多少，所以會需要另一個變數 needToAdd 來處理，有點像雙指標的概念，max 永遠紀錄最大值，而當觸發統一時 needToAdd 會即時跟上 max。

最後，因為有可能有 M 中的元素完全沒被加過，你沒辦法幫他處理統一，所以你還需要遍歷一次 M，將 M 沒被統一的值做統一，因此所需的時間複雜度就是 N 和 M 個只遍歷一次，為 O(N+M)。

這題在 Codility 算 medium，感覺確實比起其他 Lesson 更有挑戰一點，不過以體感來說應該還是只有 LeetCode 的 easy 難度而已。

  • 時間複雜度 O(N+M)
  • 空間複雜度 O(M)

PHP 程式碼：