題目連結:
題目意譯:
給定一個包含著 n 個整數的整數陣列 nums,請計算出每一個大小為 k 的子陣列之「美麗度」。
一個子陣列的「美麗度」為該子陣列中的第 x 小整數之值(如果該數為負數);如果當中少於 x 個負數,則美麗度為 0。
回傳一個包含 n - k + 1 個整數的整數陣列,其代表著每一個子陣列的美麗度(以每一個子陣列的開頭索引值依序陳列)。
一個子陣列為一陣列中一段連續非空之元素序列。
限制:
n == nums.length
1 ≦ n ≦ 10 ^ 5
1 ≦ k ≦ n
1 ≦ x ≦ k
-50 ≦ nums[i] ≦ 50
範例測資:
範例 1:
輸入: nums = [1,-1,-3,-2,3], k = 3, x = 2
輸出: [-1,-2,-2]
解釋: 現在有 3 個大小為 k = 3 的子陣列。
第一個子陣列為 [1, -1, -3],而第 2 小的負數為 -1。
第一個子陣列為 [-1, -3, -2],而第 2 小的負數為 -2。
第一個子陣列為 [-3, -2, 3],而第 2 小的負數為 -2。
範例 2:
輸入: nums = [-1,-2,-3,-4,-5], k = 2, x = 2
輸出: [-1,-2,-3,-4]
解釋: 現在有 4 個大小為 k = 2 的子陣列。
對於 [-1, -2],第 2 小的負數為 -1。
對於 [-2, -3],第 2 小的負數為 -2。
對於 [-3, -4],第 2 小的負數為 -3。
對於 [-4, -5],第 2 小的負數為 -4。
範例 3:
輸入: nums = [-3,1,2,-3,0,-3], k = 2, x = 1
輸出: [-3,0,-3,-3,-3]
解釋: 現在有 5 個大小為 k = 2 的子陣列。
對於 [-3, 1],第 1 小的負數為 -3。
對於 [1, 2],由於不存在負數,因此美麗度為 0。
對於 [2, -3],第 1 小的負數為 -3。
對於 [-3, 0],第 1 小的負數為 -3。
對於 [0, -3],第 1 小的負數為 -3。
解題思維:
誠如題目標題所述,本題可以用滑動視窗(Sliding Window)來解,如
這題。
而由於數值範圍最小只會到 -50,因此不需要特別花俏的手段,直接維護單一視窗中每一種負數(即 -1 ~ -50)的個數。然後對於每一個視窗(即對於每一個大小為 k 的子陣列)掃過一次 -1 ~ -50 來看第 k 小的數字座落於何處即可得到該子陣列的美麗度。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。