调试中...
全部题解
Problem: 1673. 找出最具竞争力的子序列
解题方法：单调栈
先看做法，再讲原理（可能看完做法不看原理就懂了）。
方法概述
使用一个单调递增栈。和普通单调栈不同的是，本题需要同时确保：
- 单调栈中最多有个元素
- 如果要出栈，要先保证出栈后
然后问题基本上就解决了。
具体怎么做
使用一个栈用来存放最终答案，然后遍历数组：
当
栈顶元素＞当前元素且栈顶出栈后还能凑够k个时，栈顶元素不断出栈。若栈中元素个数小于k，则当前元素入栈。
遍历完成后，从栈底到栈顶的元素即为要找的答案。
为什么这么做
需要明白的是，“只要后面元素还够，遇到小的元素时小元素越往前越好”：
例如当前栈中是
[2 4 6，k = 3，剩余元素是3 1000 1000 1000 ...。当前遍历到了元素
3，后面元素足够多，那么3就应该尽量往前（把4 6都替换掉变成[2 3）。虽然
3后面的元素都很大，但是[2 3 ∞是优于[2 4 6的。
为什么“若栈中元素个数小于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评论 (0)
行 1，列 1