ETH官方钱包

前往
大廳
主題

LeetCode - 2389. Longest Subsequence With Limited Sum 解題心得

Not In My Back Yard | 2023-07-17 12:00:11 | 巴幣 0 | 人氣 140

題目連結:


題目意譯:
你被給定一個長度 n 整數(shù)陣列 nums,以及一個長度 m 的整數(shù)陣列 queries。

回傳一個長度 m 的陣列,其中 answer[i] 為你可以從 nums 擷取出來的最長子序列之長度,使得其元素總和小於等於 queries[i]。

一個子序列為一個可以從另一陣列藉由刪除若干個或零個元素並不更動到剩餘元素的相對順序而得到的陣列。

限制:
n == nums.length
m == queries.length
1 ≦ n, m ≦ 1000
1 ≦ nums[i], queries[i] ≦ 10 ^ 6



範例測資:
範例 1:
輸入: nums = [4,5,2,1], queries = [3,10,21]
輸出: [2,3,4]
解釋: 我們以下列答案來回答每筆詢問:
- 子序列 [2,1] 有著總和值小於等於 3。可以證明 2 為此種子序列的最大長度,因此 answer[0] = 2。
- 子序列 [4,5,1] 有著總和值小於等於 10。可以證明 3 為此種子序列的最大長度,因此 answer[1] = 3。
- 子序列 [4,5,2,1] 有著總和值小於等於 21。可以證明 4 為此種子序列的最大長度,因此 answer[2] = 4。

範例 2:
輸入: nums = [2,3,4,5], queries = [1]
輸出: [0]
解釋: 空子序列是唯一一個有著總和值小於等於 1 的,因此 answer[0] = 0。


解題思維:
由於我們只在乎子序列的長度以及其總和值,因此我們可以把 nums 中的數(shù)字由小排到大,而不更動到答案(即最大長度)。

而為了讓總和值盡量小,則我們應從排序後第一個元素開始挑、再挑第二個元素、……以此類推直到每個元素都被挑了或是再挑下去會超過 queries[i]。則此時的長度(即挑的數(shù)字之數(shù)量)即為 answer[i] 之值。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創(chuàng)作回應

更多創(chuàng)作