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;
    }
};