1673. Find the Most Competitive Subsequence

Problem

Given an integer array nums and a positive integer k, return the most competitive subsequence of nums of size k.

An array’s subsequence is a resulting sequence obtained by erasing some (possibly zero) elements from the array.

We define that a subsequence a is more competitive than a subsequence b (of the same length) if in the first position where a and b differ, subsequence a has a number less than the corresponding number in b. For example, [1,3,4] is more competitive than [1,3,5] because the first position they differ is at the final number, and 4 is less than 5.

Example 1:

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

Example 2:

Input: nums = [2,4,3,3,5,4,9,6], k = 4
Output: [2,3,3,4]

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 1 <= k <= nums.length

Solution

我們必須先了解題目中的 competitive subsequence 是什麼。當 a 比 b 更 competitive 時，這是指在相同的位置上，a 的字母比 b 的字母小。依據這個想法，我們可以建立一個 increasing monotonic stack 來尋找一個最小的遞增 subsequence。另外，要注意到，當 stack 的數量加上還未處理的字母數量再加上當前處理的字母，其總和大於 k 時，我們才可以 pop stack 中的字母。不然，最後會不如湊到 k 個字母。

Monotonic Stack

• Times:
• Spaces:

class Solution {
    public static int[] mostCompetitive(int[] nums, int k) {
        int[] results = new int[k];
        int pointer = -1;

        for (int i = 0; i < nums.length; i++) {
            int n = nums[i];
            while (pointer >= 0 && results[pointer] > n && pointer + (nums.length - i) >= k) {
                pointer--;
            }

            if (pointer < k - 1) {
                results[++pointer] = n;
            }
        }

        return results;
    }
}

參考

• 1673. Find the Most Competitive Subsequence, LeetCode.
• 1673. Find the Most Competitive Subsequence, LeetCode Solutions.