Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2022-12-25 14:49:56
2389. Longest Subsequence With Limited Sum
给你一个阵列nums表示一个数列,并给你一个阵列表示每次查询和的上限,从数列中找
出一个序列(不必连续)满足小于等于查询之和并且尽可能的大。
Input: nums = [4,5,2,1], queries = [3,10,21]
Output: [2,3,4]
Explanation:
第一次查询 queries[0] = 3,序列[2,1]为最长序列所以结果为2
第二次查询 queries[1] = 10,序列[4,2,1]为最长序列所以结果为3
第三次查询 queries[2] = 21,序列[4,5,2,1]为最长序列所以结果为4
思路:
1.因为序列不需要是连续的,所以我们可以每次都从整个序列中取出任意位置最小的数
字并加到sum,若sum小于等于target则长度加一,否则返回当前长度。
2.因为要每次都取出最小数字所以我们可以将原阵列先做排序,并查询n次即可。
Java Code:
作者: koy784512 (我永远喜欢风真いろは)   2022-12-25 15:03:00
大师
作者: pandix (面包屌)   2022-12-25 15:21:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com