最值问题
2026-09-06 18:04:21
发布于:上海
最值问题信号
贪心信号
关键词:“最多”“最少”“最大”“最小”。
特征:排序后有单调性、每步选择只看当前状态、各元素之间独立或仅有简单约束。
时间复杂度:O(nlogn),N ≤ 1e6,时间开销主要在排序上。
DP信号
关键词:“最大价值”“最小奶牛数”“能到达的最高音量”“恰好”“方案数”。
特征:有约束导致选择冲突,一个选择会影响另一个选择的可行性。
时间复杂度:O(nm),N,M ≤ 1e4/1e3。
二分信号
关键词:“最大值最小”“最小值最大”。
特征:给一个最值定义,求这个最值定义的最大化/最小化。
时间复杂度:O(nlogn),N ≤ 1e6,logn:二分,n:循环。
这里空空如也




















有帮助,赞一个