Leetcode_1673_找出最具竞争力的子序列_单调栈

12/12

以前做过一道几乎一模一样的题,一眼就看出来是维护一个单调栈
然后把之前的那篇博客翻出来,复制黏贴->大于号改小于号->通过了????
class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        int n=nums.length;
        int []stack = new int[k];
        //栈顶指针
        int top = -1;
        //除掉k个元素外的数组剩余元素
        int remain = n - k;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            //退栈
            while (top >= 0 && stack[top] > num && remain > 0) {
                top--;
                //退栈的话会导致剩余元素减少
                remain--;
            }
            if (top < k - 1) {
                stack[++top] = num;
            } else {
                //stack[top]<=num,该元素直接扔掉
                remain--;
            }
        }
        return stack;
    }
}

版权声明:本文为HDUCheater原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。