class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
}
};
1673. 找出最具竞争力的子序列
给你一个整数数组 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 <= 1050 <= nums[i] <= 1091 <= k <= nums.length原站题解
php 解法, 执行用时: 376 ms, 内存消耗: 31.1 MB, 提交时间: 2024-05-24 09:41:00
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer[]
*/
function mostCompetitive($nums, $k) {
$stack = [];
$n = count($nums);
$last = $n - $k;
for ( $i = 0; $i < $n ; $i++ ) {
while ( !empty($stack) && $last > 0 && end($stack) > $nums[$i] ) {
array_pop($stack);
$last--;
}
$stack[] = $nums[$i];
}
return array_slice($stack, 0, $k);
}
}
javascript 解法, 执行用时: 140 ms, 内存消耗: 76.4 MB, 提交时间: 2024-05-24 09:32:37
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var mostCompetitive = function(nums, k) {
const st = [];
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
while (st.length && x < st[st.length - 1] && st.length + nums.length - i > k) {
st.pop();
}
if (st.length < k) {
st.push(x);
}
}
return st;
};
rust 解法, 执行用时: 40 ms, 内存消耗: 3.6 MB, 提交时间: 2023-09-25 11:07:19
impl Solution {
pub fn most_competitive(nums: Vec<i32>, k: i32) -> Vec<i32> {
let k = k as usize;
let n = nums.len();
let mut stack = vec![];
let mut j = 0;
for i in 0..n {
while stack.len() > 0 && stack[stack.len()-1] > nums[i] && k + j < n {
stack.pop();
j += 1;
}
stack.push(nums[i]);
}
stack[0..k].to_vec()
}
}
golang 解法, 执行用时: 144 ms, 内存消耗: 9.1 MB, 提交时间: 2023-09-25 11:06:54
func mostCompetitive(nums []int, k int) []int {
stack := []int{}
n := len(nums)
last := n-k
for i := 0; i < n ; i ++ {
for len(stack) > 0 && last > 0 && stack[len(stack)-1] > nums[i] {
stack = stack[:len(stack)-1]
last--
}
stack = append(stack, nums[i])
}
return stack[:k]
}
python3 解法, 执行用时: 200 ms, 内存消耗: 28.7 MB, 提交时间: 2023-09-25 11:06:34
class Solution:
def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
stack = []
n = len(nums)
last = n-k
for i in range(n):
while stack and last and stack[-1] > nums[i]:
stack.pop()
last -= 1
stack.append(nums[i])
return stack[:k]
java 解法, 执行用时: 17 ms, 内存消耗: 57.1 MB, 提交时间: 2023-09-25 11:06:19
class Solution {
public int[] mostCompetitive(int[] nums, int k) {
ArrayList<Integer> stack = new ArrayList<Integer>();
int n = nums.length;
int last = n-k;
for (int i = 0; i < n; i ++) {
while (stack.size()>0 && last>0 && stack.get(stack.size()-1)>nums[i]) {
stack.remove(stack.size()-1);
last --;
}
stack.add(nums[i]);
}
int[] res = new int[k];
for(int i = 0; i < k; i++){
res[i] = stack.get(i);
}
return res;
}
}
cpp 解法, 执行用时: 208 ms, 内存消耗: 108.9 MB, 提交时间: 2023-09-25 11:06:04
/**
* 从左至右找到第一个逆序对，使得s[i]>s[i+1],维护一个单调栈，栈内元素单调不减，
* 将s[i]删除才能使得最后字典序更小，注意可以删除的个数为n-k个。
*/
class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
vector<int> stk;
int n = nums.size();
int last = n - k;
for (int i = 0; i < n; i ++)
{
while (!stk.empty() && last > 0 && stk.back() > nums[i])
{
stk.pop_back();
last --;
}
stk.push_back(nums[i]);
}
for (int i = 0; i < last; i ++)
{
stk.pop_back();
}
return stk;
}
};