LeetCode 1673. 找出最具竞争力的子序列
原题链接
中等
作者:
ACSaber
,
2020-12-06 17:30:28
,
所有人可见
,
阅读 472
class Solution {
public int[] mostCompetitive(int[] nums, int k) {
int n = nums.length;
if (k == n) return nums;
int t = n - k;
Deque<Integer> stack = new ArrayDeque<Integer>();
for (int i = 0; i < n; i++) {
while (t > 0 && !stack.isEmpty() && nums[stack.peekLast()] > nums[i]) {
stack.pollLast();
t--;
}
stack.addLast(i);
}
int[] ans = new int[k];
int idx = 0;
while (k > 0) {
ans[idx++] = nums[stack.pollFirst()];
k--;
}
return ans;
}
}