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

【LetMeFly】1673.找出最具竞争力的子序列：单调栈（贪心）

力扣题目链接：https://leetcode.cn/problems/find-the-most-competitive-subsequence/

给你一个整数数组 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 <= 105
• 0 <= nums[i] <= 109
• 1 <= k <= nums.length

解题方法：单调栈

先看做法，再讲原理（可能看完做法不看原理就懂了）。

方法概述

使用一个单调递增栈。和普通单调栈不同的是，本题需要同时确保：

1. 单调栈中最多有$k$个元素
2. 如果要出栈，要先保证出栈后$栈中元素+剩余元素\geq k$

然后问题基本上就解决了。

具体怎么做

使用一个栈$st$用来存放最终答案，然后遍历数组：

当栈顶元素＞当前元素且栈顶出栈后还能凑够k个时，栈顶元素不断出栈。

若栈中元素个数小于k，则当前元素入栈。

遍历完成后，从栈底到栈顶的元素即为要找的答案。

为什么这么做

需要明白的是，“只要后面元素还够，遇到小的元素时小元素越往前越好”：

例如当前栈中是[2 4 6，k = 3，剩余元素是3 1000 1000 1000 ...。

当前遍历到了元素3，后面元素足够多，那么3就应该尽量往前（把4 6都替换掉变成[2 3）。

虽然3后面的元素都很大，但是[2 3 ∞是优于[2 4 6的。

为什么“若栈中元素个数小于k，则当前元素入栈”：

因为“若当前元素较小”或者“栈中元素不是很足”，那当前元素当然要入栈。

否则（栈中元素数量为$k$）的话，说明当前元素很大，没给栈中元素弹出来，当前元素不值得入栈。

时空复杂度

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(k)$，栈中最多同时存在$k$个元素

AC代码

C++

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        stack<int> st;
        for (int i = 0; i < nums.size(); i++) {
            while (st.size() && st.top() > nums[i] && (st.size() - 1) + (nums.size() - i) >= k) {
                st.pop();
            }
            if (st.size() < k) {
                st.push(nums[i]);
            }
        }
        // stack -> vector
        vector<int> ans;
        while (st.size()) {
            ans.push_back(st.top());
            st.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Java

// import java.util.ArrayDeque;
// import java.util.Deque;

class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        Deque<Integer> st = new ArrayDeque<Integer>();
        for (int i = 0; i < nums.length; i++) {
            while (!st.isEmpty() && st.peek() > nums[i] && (st.size() - 1) + (nums.length - i) >= k) {
                st.pop();
            }
            if (st.size() < k) {
                st.push(nums[i]);
            }
        }
        // stack -> array
        int[] ans = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            ans[i] = st.pop();
        }
        return ans;
    }
}

Python

# from typing import List

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        st = []
        for i in range(len(nums)):
            while st and st[-1] > nums[i] and (len(st) - 1) + (len(nums) - i) >= k:
                st.pop()
            if len(st) < k:
                st.append(nums[i])
        return st

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/139185554