{"id":7736,"date":"2020-11-29T02:11:47","date_gmt":"2020-11-29T10:11:47","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7736"},"modified":"2020-11-29T02:15:36","modified_gmt":"2020-11-29T10:15:36","slug":"leetcode-1673-find-the-most-competitive-subsequence","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/uncategorized\/leetcode-1673-find-the-most-competitive-subsequence\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1673. Find the Most Competitive Subsequence"},"content":{"rendered":"\n

Given an integer array nums<\/code> and a positive integer k<\/code>, return the most competitive<\/strong> subsequence of <\/em>nums<\/code> of size <\/em>k<\/code>.<\/p>\n\n\n\n

An array’s subsequence is a resulting sequence obtained by erasing some (possibly zero) elements from the array.<\/p>\n\n\n\n

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

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> nums = [3,5,2,6], k = 2\nOutput:<\/strong> [2,6]\nExplanation:<\/strong> 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.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [2,4,3,3,5,4,9,6], k = 4\nOutput:<\/strong> [2,3,3,4]\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= nums.length <= 105<\/sup><\/code><\/li>
  • 0 <= nums[i] <= 109<\/sup><\/code><\/li>
  • 1 <= k <= nums.length<\/code><\/li><\/ul>\n\n\n\n
    Solution: Stack<\/strong><\/h2>\n\n\n\n
    Use a stack to track the best solution so far, pop if the current number is less than the top of the stack and there are sufficient numbers left. Then push the current number to the stack if not full.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(k)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector mostCompetitive(vector& nums, int k) {\n    const int n = nums.size();\n    vector ans(k);\n    int c = 0;\n    for (int i = 0; i < n; ++i) {\n      while (c && ans[c - 1] > nums[i] && c + n - i - 1 >= k) \n        --c;\n      if (c < k) ans[c++] = nums[i];\n    }\n    return ans;\n  }\n};\n<\/pre>\n\n<\/div>
    Java<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\n  public int[] mostCompetitive(int[] nums, int k) {\n    int n = nums.length;\n    int[] ans = new int[k];\n    int c = 0;\n    for (int i = 0; i < n; ++i) {\n      while (c > 0 && ans[c - 1] > nums[i] && c + n - i - 1 >= k)\n        --c;\n      if (c < k) ans[c++] = nums[i];\n    }\n    return ans;\n  }\n}\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \n# Author: Huahua\nclass Solution:\n  def mostCompetitive(self, nums: List[int], k: int) -> List[int]:\n    ans = [None] * k\n    n = len(nums)\n    c = 0\n    for i, x in enumerate(nums):\n      while c and ans[c - 1] > x and c + n - i - 1 >= k:\n        c -= 1\n      if c < k: \n        ans[c] = x\n        c += 1\n    return ans\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-7736","post","type-post","status-publish","format-standard","hentry","category-uncategorized","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7736","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7736"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7736\/revisions"}],"predecessor-version":[{"id":7738,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7736\/revisions\/7738"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7736"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7736"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7736"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}