Loading... > https://leetcode.cn/problems/find-the-most-competitive-subsequence/description/?envType=daily-question&envId=2024-05-06 易知最具竞争力的子序列一定是有序的，并且越前面的数权重越大，应该尽可能小，所以可以用单调栈来求解。 注意第 $i$ 个位置需要预留 $k - i$ 个元素，不然无法构建出合规的子序列。 ```c++ class Solution { public: std::vector<int> mostCompetitive(std::vector<int>& nums, int k) { const int n = nums.size(); std::vector<int> res; for (int i = 0; i < n; i++) { while (!res.empty() && n - i + res.size() > k && res.back() > nums[i]) res.pop_back(); if (res.size() < k) res.push_back(nums[i]); } return res; } }; ``` - 时间复杂度：$O(n)$ ，其中 $n$ 为数组 `nums` 的大小。 - 空间复杂度：$O(1)$ ，除了返回值所占的空间只有常数级的变量。 最后修改：2024 年 05 月 24 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏