LeetCode-Go 题解 1673单调栈求最具竞争力子序列Find the Most Competitive Subsequence【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南以 LeetCode-Go 仓库中 1673. Find the Most Competitive Subsequence 的官方题解文档为核心完整拆解最具竞争力子序列的数学定义、单调栈解法的正确性依据、仓库内 Go 源码的实现细节与测试用例验证方式。读完本文你将掌握如何用 O(n) 时间在保持元素相对顺序的前提下求出字典序最小的长度为 k 的子序列并能举一反三迁移到仓库中其他单调栈题型。题目理解什么是最具竞争力的子序列给定一个整数数组nums和一个正整数k要求返回长度为k且最具竞争力most competitive的nums子序列。子序列subsequence是从原数组中删除若干元素可以一个都不删后得到的序列元素的相对顺序必须保持不变——只能删除不能移动也不能交换位置。竞争力的比较规则是对于两个长度相同的子序列a和b在它们第一个出现差异的位置上如果a中的数字小于b中对应的数字则称a比b更具竞争力。例如[1,3,4]比[1,3,5]更具竞争力两个子序列在前两个位置1、3完全相同第一个差异出现在最后一个位置而4 5。关键等价关系竞争力 ⇔ 字典序最小将两个子序列视为数字序列逐位比较规则是第一个不同位置上数字更小者胜这与字典序lexicographical order的定义完全一致。因此本题等价于在保持元素相对顺序的前提下求nums的所有长度为k的子序列中字典序最小的那一个。这一等价关系是理解后续所有解法的钥匙——我们要做的不是找最小元素而是贪心地让每一位尽可能小。约束条件原文档给出的约束如下1 nums.length 10^50 nums[i] 10^91 k nums.length数组规模达到 10^5意味着暴力枚举所有 C(n, k) 种子序列完全不可行必须设计线性或近线性的算法。两个官方示例示例 1Input: nums [3,5,2,6], k 2 Output: [2,6]所有可能的长度为 2 的子序列为{[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}其中[2,6]最具竞争力第一位2已经是所有候选中最小的。示例 2Input: nums [2,4,3,3,5,4,9,6], k 4 Output: [2,3,3,4]注意这个结果并不是简单取最小的 4 个元素那会得到[2,3,3,4]恰好重合也不是取尽量靠前的最小元素[2,3,3,5]就不如[2,3,3,4]需要在每一位上做全局权衡。解题思路为什么单调栈是正确答案原文档明确指出这一题是单调栈的典型题型。核心论据有两条单调栈天然保持相对顺序栈的操作是从尾部弹出、从尾部压入弹出的只是已扫描区间的元素从不会打乱原数组的相对位置关系恰好满足删除元素但不移动元素的子序列约束单调栈保证每次进栈时元素尽量小扫描过程中若新元素比栈顶更小且弹出后仍有足够元素凑满 k 个就果断弹出栈顶让更小的元素占据更靠前的位置从而实现字典序贪心。弹出条件的核心余量守卫这里有一个容易忽略的细节不能无脑弹出所有比nums[i]大的栈顶元素。因为最终必须凑满k个元素如果弹得太多剩余元素不够补位就无法形成合法答案。仓库中的 Go 实现源码文件把这条守卫写进了循环条件package leetcode // 单调栈 func mostCompetitive(nums []int, k int) []int { stack : make([]int, 0, len(nums)) for i : 0; i len(nums); i { for len(stack)len(nums)-i k len(stack) 0 nums[i] stack[len(stack)-1] { stack stack[:len(stack)-1] } stack append(stack, nums[i]) } return stack[:k] }逐个条件拆解内层fornums[i] stack[len(stack)-1]只有新元素比栈顶当前已选序列的最后一位更小时替换才有收益否则保留原栈顶相等也不弹保证稳定len(stack) 0栈空时无处可弹len(stack)len(nums)-i k余量守卫。len(stack)是当前栈中已选元素个数len(nums)-i是包括nums[i]在内的剩余可选元素个数。二者之和严格大于k意味着即使现在弹出一个元素后续也依然有足够元素可以补满 k 个因此这次弹出是安全的反之若二者之和已经等于k或小于则不能再弹否则永远凑不满k个元素。扫描结束后栈中可能残留多于k个元素例如原数组单调递增、全程未发生弹出时栈会长到len(nums)此时直接截取前k个return stack[:k]。因为栈的头部始终保持着字典序贪心下的最优前缀尾部多出来的元素只可能是被余量守卫强制保留的多余尾巴。从源码细节看工程习惯栈用make([]int, 0, len(nums))一次性预分配容量避免append过程中的多次扩容在 10^5 规模下能明显减少内存分配开销函数名为小写mostCompetitive包内私有与仓库中绝大多数题解函数保持一致的命名风格测试文件与它同处于leetcode包内因此可以直接调用代码与文档中的解题思路一一对应注释// 单调栈直接点明题型。算法正确性推演手动走查三个用例走查示例 1nums [3,5,2,6],k 2inums[i]弹栈前 stack是否弹出弹栈后 stack03[]否栈空[3]15[3]否5 ≥ 3[3,5]22[3,5]弹出 5、32 更小且余量 224 2[2]36[2]否余量 112不满足 2[2,6]第 3 步是精髓2比栈顶5小且弹出后剩余元素2、6仍能凑满 2 个于是连弹5、3到第 4 步6虽比栈顶2大但此时栈中 1 个元素 剩余 1 个元素刚好等于k一旦弹出就凑不齐只能保留。最终返回[2,6]。走查示例 2nums [2,4,3,3,5,4,9,6],k 4inums[i]弹栈前 stack弹出动作弹栈后 stack02[]—[2]14[2]无4 ≥ 2[2,4]23[2,4]弹出 4[2,3]33[2,3]无3 ≥ 3相等不弹[2,3,3]45[2,3,3]无5 ≥ 3[2,3,3,5]54[2,3,3,5]弹出 5[2,3,3,4]69[2,3,3,4]无9 ≥ 4[2,3,3,4,9]76[2,3,3,4,9]弹出 9[2,3,3,4,6]注意第 3 步3与栈顶3相等时不弹出——因为弹出后换上的还是同样的值没有任何收益反而会消耗余量。扫描结束时栈为[2,3,3,4,6]5 个元素截取前 4 个得到答案[2,3,3,4]尾部多余的6正是被余量守卫保留的尾巴。走查测试用例 4nums [71,18,52,29,55,73,24,42,66,8,80,2],k 3重点看结尾三位的处理扫描到8时它比栈中所有元素都小且余量充足于是栈被清空重建为[8]随后80入栈最后一个元素2比栈顶80小但此时栈中 2 个元素 剩余 1 个元素 3恰好等于k余量守卫禁止弹出于是栈最终为[8,80,2]答案正确。这个用例非常有价值它证明栈中元素并非全局单调[8,80,2]并不是非递减的单调性只在余量允许的区间内成立。这也解释了为什么不能把本题简化为单调栈去重或取最小 k 个元素必须始终把余量守卫纳入考量。复杂度分析时间复杂度 O(n)每个元素至多入栈一次、出栈一次内层for的总弹出次数不超过 n整体为线性扫描空间复杂度 O(n)栈预分配了len(nums)容量最坏情况如原数组单调递增、几乎不发生弹出栈会占满 n 个元素。在n 10^5的约束下O(n) 的时空开销完全可行。测试用例与本地验证仓库为该题配备了完整的单元测试测试文件文件名为1673. Find the Most Competitive Subsequence_test.go采用仓库统一的question1673 / para1673 / ans1673结构体组织测试数据。测试共覆盖 5 组用例输入numsk期望输出[3,5,2,6]2[2,6][2,4,3,3,5,4,9,6]4[2,3,3,4][2,4,3,3,5,4,9,6]4[2,3,3,4][71,18,52,29,55,73,24,42,66,8,80,2]3[8,80,2][84,10,71,...,95,71]28 个元素2424 个元素的较长序列其中第 3 组与第 2 组重复第 4、5 组则覆盖了余量守卫强制保留较大元素和长数组 大 k两种边界场景直接考验单调栈实现是否会在弹栈时弹出过头。本地运行方式项目根目录下# 只跑本题的测试 go test -v -run Test_Problem1673 ./leetcode/1673.Find-the-Most-Competitive-Subsequence/ # 跑整个仓库并生成覆盖率 ./gotest.sh其中gotest.sh内部执行go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性对leetcode下所有题解包生成统一格式的覆盖率文件。运行本题测试时测试函数会通过fmt.Printf逐组打印【input】与【output】便于直观核对。单调栈题型在仓库中的延伸原文档在解题思路一节列出了同类题型第 42、84、496、503、856、901、907、1130、1425、1673 题。这些题目在本仓库中大多都有完整题解与测试可对照阅读强化对单调栈维护候选区间极值这一核心思想的掌握0042. Trapping Rain Water用单调栈计算接水量体会维护递减栈 弹出时结算的经典模式0084. Largest Rectangle in Histogram单调递增栈 弹出时计算矩形面积是栈内结算时机的教科书案例0496. Next Greater Element I 与 0503. Next Greater Element II单调栈求下一个更大元素的入门模板0856. Score of Parentheses用栈处理括号匹配与计分0901. Online Stock Span单调栈求连续不大于当日价格的天数跨度0907. Sum of Subarray Minimums单调栈求所有子数组最小值之和与本题找每一位上尽可能小的元素思路一脉相承。此外与本题思路最接近的仓库内题目当属 9990316. Remove Duplicate LettersLeetCode 316 题它同样使用单调栈求字典序最小的子序列区别仅在于要求每个字符最多出现一次、且必须保留所有不同字符。对照两道题可以清晰看到单调栈 剩余可用元素预算这一通用框架在两种约束下的变形。小结LeetCode 1673 的核心考点可以浓缩为三句话识别题型第一个不同位置上数字更小即字典序最小目标变为求字典序最小的长度为 k 的子序列选择工具单调栈天然保持元素相对顺序配合弹出时比较栈顶即可贪心地让每一位尽可能小守住底线余量守卫len(stack)len(nums)-i k保证任何时刻的弹出都不会导致最终凑不满 k 个元素这是代码正确性的关键也是与普通单调栈去重题的本质区别。仓库中的 源码实现 仅十余行却浓缩了单调栈、贪心与余量约束三者协同的完整思路配合 测试文件 中的五组用例可以在本地一键复现并验证算法的正确性。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
