leetcode.5614. 找出最具竞争力的子序列

古城微笑少年丶 2022-12-24 15:52 107阅读 0赞

# 5614. 找出最具竞争力的子序列 #

给你一个整数数组 `nums` 和一个正整数 `k` ，返回长度为 `k` 且最具 竞争力 的 `nums` 子序列。

数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。

在子序列 `a` 和子序列 `b` 第一个不相同的位置上，如果 `a` 中的数字小于 `b` 中对应的数字，那么我们称子序列 `a` 比子序列 `b`（相同长度下）更具 竞争力 。 例如，`[1,3,4]` 比 `[1,3,5]` 更具竞争力，在第一个不相同的位置，也就是最后一个位置上， `4` 小于 `5` 。

示例 1：

输入：nums = [3,5,2,6], k = 2
    输出：[2,6]
    解释：在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 最具竞争力。

示例 2：

输入：nums = [2,4,3,3,5,4,9,6], k = 4
    输出：[2,3,3,4]

提示：

1 <= nums.length <= 10^5
    0 <= nums[i] <= 10^9
    1 <= k <= nums.length

# 代码与思路 #

我们观察题目给出的例子，不难发现，这是一个TOP K问题。  
例子1

输入：nums = [3,5,2,6], k = 2
    输出：[2,6]
    解释：在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 最具竞争力。

例子2

输入：nums = [2,4,3,3,5,4,9,6], k = 4
    输出：[2,3,3,4]

返回值都是最小的K位数，所以，不难发现这个问题跟[移掉K位数字][K]的问题相似

"移掉K位数字"例子1

输入: num = "1432219", k = 3
    输出: "1219"
    解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

"移掉K位数字"例子2

输入: num = "10200", k = 1
    输出: "200"
    解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

只不过"移掉K位数字"问题是一个字符串，这个问题给的是一个数组。  
我们用数组的长度减去移掉的K位数字，得到的就是要保留的数字了。

package weekly_contest_217;
    
    import java.util.ArrayDeque;
    import java.util.Arrays;
    import java.util.Deque;
    
    //5614. 找出最具竞争力的子序列
    //参考——402. 移掉K位数字
    public class Solution2 { 
    	
        public int[] mostCompetitive(int[] nums, int k) { 
        	int[] res = new int[k];
        	k = nums.length-k;
    		// 使用双端队列来代替栈
    		Deque<Integer> deque = new ArrayDeque<Integer>();
    		// 栈顶元素大于当前元素就移除
    		int length = nums.length;
    		for (int i = 0; i < length; ++i) { 
    			int digit = nums[i];
    			while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) { 
    				deque.pollLast();
    				k--;
    			}
    			deque.offerLast(digit);
    		}
    
    		// 如果我们删除了 m 个数字且m<k，这种情况下我们需要从序列尾部删除额外的 k−m 个数字
    		for (int i = 0; i < k; ++i) { 
    			deque.pollLast();
    		}
    
    		// 返回
    		int j = 0;
    		while (!deque.isEmpty()) { 
    			int digit = deque.pollFirst();
    			res[j] = digit;
    			j++;
    		}
    		
    		return res;
        }
        
        
        
        public static void main(String[] args) { 
    		int[] nums = { 2,4,3,3,5,4,9,6};
    		int k = 2;
    		int[] arr = new Solution2().mostCompetitive(nums, k);
    		System.out.println(Arrays.toString(arr));
    		
    // int[] nums = {3,5,2,6};
    // int k = 2;
    // int[] arr = new Solution2().mostCompetitive(nums, k);
    // System.out.println(Arrays.toString(arr));
    	}
    }

# 参考资料 #

[移掉K位数字][K]

[K]: https://blog.csdn.net/e891377/article/details/109704470