最值问题
2026-09-05 18:41:44
发布于:上海
:
贪心信号:
关键词:"最多","最少","最大","最小"
特征:排序后有单调性、每步选择只看当前状态、各元素之间独立或仅有简单约束。
验证:交换验证(找反例)
典型场景:按某个属性排序后依次选取;每次选当前最优且不影响后续最优性。
时间复杂度:O(nlogn) (开销主要在排序),N ≤ 1e6
DP信号:
关键词:"恰好","方案数","最大价值"。
特征:有约束导致选择冲突、一个选择会影响另一个选择的可行性。
验证:先假设贪心,看看能否构造"贪心选了A导致错过更好的B的情况"。
典型场景:背包问题、序列选择、区间问题。
时间复杂度:O(n 2)以上
二分信号:
关键词:"最大值最小"、"最小值最大"。
套路:二分模板+check函数。
典型场景:"最短距离最大化"、"最大段和最小化"。
时间复杂度:O(nlogn) (n开销在check函数,log n 开销在二分) (N ≤ 1e6)。
技巧:看到最值问题,先猜贪心,如果贪心交换论证(找反例)出错,考虑DP、二分。
这里空空如也





















有帮助,赞一个