【单调栈】找出最具竞争力的子序列

/** 单调栈；每次取得数据都比上一次的更小
 * @auther start
 * @create 2023-12-12 22:18
 */
public class L1673 {
    public int[] mostCompetitive(int[] nums, int k) {
        int len = nums.length;
//        表示可以出栈的次数，如果delete小于0说明栈中的个数小于k
        int delete = len - k;
        Deque<Integer> stack = new LinkedList<>();
        //遍历数组，
        for (int i = 0; i < len; i++) {
//            栈不为空，栈顶元素较大，delete>0，则栈顶元素出栈
            while (!stack.isEmpty() && stack.peek() > nums[i] && delete > 0) {
                stack.pop();
                delete--;
            }
            stack.push(nums[i]);
        }
//        此时delete大于0说明栈中的元素大于k。需要出栈
        while (delete > 0) {
            stack.pop();
            delete--;
        }
        int res[] = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            res[i] = stack.pop();
        }
        return res;
    }
}