最值问题
2026-09-05 19:02:52
发布于:上海
1.识别信号:
贪心信号:
关键词:最多 最少 最大 最小
特征:排序后有单调性,每步选择只需要考虑当下最优解即可
验证:交换论证可以证明贪心的正确性
典型场景:按某个属性排序后遍历,每次只考虑当下的最优解且不影响后续的最优性
时间复杂度:O() ,时间开销主要在排序
DP信号:
关键词:最大或最小 恰好 方案数
特征:有约束导致选择冲突,贪心策略会找到反例,一个选择会影响另一个选择的可行性
验证:举反例——尝试贪心看看能不能构造出”贪心选了A导致错过更好的B的情况“
典型场景:序列选择(前面的数字选或不选会影响后面),背包(容量有限,每个物品要考虑拿或者不拿,每个决策都会影响后续的选择),区间问题(只能操作相邻的区间元素)
时间复杂度:一般大于O() , N <= 1e4
二分信号:
关键词 最大值最小 最小值最大
套路:二分答案+check函数
典型场景:最短距离最大化 最大段和最小化
时间复杂度:O(),
技巧:看到最值问题 先猜贪心 交换论证一下 验证通过选贪心 否则转dp或二分
举反例
这里空空如也





















有帮助,赞一个