1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int[] mostCompetitive(int[] nums, int k) {
Stack<Integer> increaseStack = new Stack<>();
for (int i = 0; i < nums.length; i++) {
while (!increaseStack.isEmpty() && increaseStack.size() + (nums.length - i) > k && nums[i] < nums[increaseStack.peek()]) {
increaseStack.pop();
}
increaseStack.push(i);
}
int[] ans = new int[k];
while (increaseStack.size() > k) {
increaseStack.pop();
}
for (int i = k - 1; i >= 0; i--) {
ans[i] = nums[increaseStack.pop()];
}
return ans;
}
}
|
关键点在于移除栈中的元素前需要判断栈中的元素数量加上剩余的元素数量需要大于 k，才能保证最后栈中剩余的元素数量大于等于 k。关键表达式：increaseStack.size() + (nums.length - i) > k
References
1673. Find the Most Competitive Subsequence