首页 > 其他分享 >1673. 找出最具竞争力的子序列

1673. 找出最具竞争力的子序列

时间:2023-04-03 12:01:44浏览次数:34  
标签:last nums int stk 最具 序列 单调 1673

题目描述

在一个数组中找出长度k的子序列,使其字典序最小?

f1-单调栈

基本分析

  1. 字典序最小肯定是单调不减最好,但是怎么保证序列的长度是k?需要删除的个数是n-k,利用单调栈同时维护这个信息,超过了就不再维护有序性了。
  2. stk中最终的结果有没有可能多于k?可能的,比如本身就是单调不减,会在stk中一直加。

代码

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        stk = []
        n = len(nums)
        last = n - k

        for i in range(n):
            while stk and last and stk[-1] > nums[i]:
                stk.pop()
                last -= 1
            stk.append(nums[i])
        
        return stk[:k]

总结

  1. 利用单调栈维护前面的单调不减的特性
  2. 利用另一个参数保证长度为k
  3. stk长度可能会超过k,注意取切片

标签:last,nums,int,stk,最具,序列,单调,1673
From: https://www.cnblogs.com/zk-icewall/p/17282685.html

相关文章

  • Java 序列化详解
    XML和JSON是两种经常在网络使用的数据表示格式,这里我们介绍如何使用Java读写XML和JSON。 一、XML概述1、XML简介我们都知道对象是不能在网络中直接传输的,不过还有补救的办法。XML(ExtensibleMarkupLanguage)可扩展标记语言,本身就被设计用来存储数据,任何一个对象都可以用XML来描......
  • 【深度学习时间序列预测案例】零基础入门经典深度学习时间序列预测项目实战(附代码+数
    前言......
  • 序列比对
    在ncbi上搜索SARS-CoV-2、SARS-CoV(2003)及RaTG13病毒株的S(Spike)蛋白质序列,在clustalOmega进行序列比对,得到的结果发现三种蛋白序列一致性很高,序列仅有少部分有差异,其中SARS-CoV(2003)及RaTG13病毒株的S(Spike)蛋白质序列更接近   ......
  • Acwing 799.最长连续不重复子序列
    原题链接代码#include<iostream>usingnamespacestd;constintN=100010;inta[N],f[N];intmain(){intn;cin>>n;intans=0,j=1;for(inti=1;i<=n;i++){scanf("%d",&a[i]);//读入该数组f[......
  • django 中model 的序列换
    方法一:from django.core import serializers ret = models.BookType.objects.all() data = serializers.serialize("json",ret) 方法二:当只有一个object时:fromdjango.forms.modelsimportmodel_to_dictdata=model_to_dict(yourmodelobject)......
  • 二叉搜索树的后序遍历序列
    classSolution{public:booldfs(vector<int>q,intl,intr){if(l>=r)returntrue;introot=q[r];intidx=l;for(;idx<r;idx++)if(q[idx]>root)break;intt=idx;......
  • 最长上升子序列 II
    最长上升子序列II题目描述给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。输入格式第一行包含整数N。第二行包含N个整数,表示完整序列。输出格式输出一个整数,表示最大长度。数据范围1≤N≤100000-10^9≤数列中的数≤10^9输入样例:73......
  • 开心档之MySQL 序列使用
    MySQL序列使用MySQL序列是一组整数:1,2,3,...,由于一张数据表只能有一个字段自增主键,如果你想实现其他字段也实现自动增加,就可以使用MySQL序列来实现。本章我们将介绍如何使用MySQL的序列。使用AUTO_INCREMENTMySQL中最简单使用序列的方法就是使用MySQLAUTO_INCREMEN......
  • day31 打卡455.分发饼干 376. 摆动序列 53. 最大子数组和
    day31打卡455.分发饼干376.摆动序列53.最大子数组和455.分发饼干455题目链接classSolution{publicintfindContentChildren(int[]g,int[]s){intcount=0;Arrays.sort(g);Arrays.sort(s);intgIndex=0;ints......
  • 代码随想录day 31 455.分发饼干 | 376. 摆动序列 | 53. 最大子序和
    455.分发饼干假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干j,都有一个尺寸s[j] 。如果s[j] >=g[i],我们可以将这个饼干j分配给孩子i,这个孩......