LeetCode 风格问题实战：贪心策略求解「最佳销售单价」的 3 个关键步骤-平芜编程栈

LeetCode 风格问题实战：贪心策略求解「最佳销售单价」的 3 个关键步骤

当我们在技术面试中遇到优化类问题时，如何快速识别问题本质并选择正确的算法策略？让我们通过一个典型的拍卖定价问题，拆解贪心算法的实战应用框架。这个问题看似简单，却蕴含着算法思维中策略选择与数学证明的核心逻辑链。

1. 问题重述与形式化建模

假设你是一位农场主，手中有m批干草需要拍卖出售。现有n位顾客，每位顾客对单批干草的报价存储在数组prices中。我们需要确定一个最优单价p：

所有报价 ≥p的顾客将以单价p各购买 1 批干草
总销售量不超过m批
目标：最大化总收益（单价 × 销量）
约束：当存在多个p能获得相同最大收益时，选择最小的单价

关键变量关系：

def calculate_profit(prices, m, p): buyers = sum(1 for x in prices if x >= p) # 符合报价的顾客数 sold = min(buyers, m) # 实际销售量 return p * sold # 总收益

这个模型实际上抽象了价格歧视策略的经济学场景。通过形式化定义，我们将现实问题转化为可计算的数学表达式，这是算法思维的第一步突破。

2. 贪心策略的可行性证明

为什么排序后枚举单价能保证最优解？这需要从子结构性质和贪心选择性质两个维度进行论证。

2.1 最优子结构分析

将报价数组排序后得到[a₁ ≤ a₂ ≤ ... ≤ aₙ]，当我们选择p = aᵢ时：

有效买家数量为n - i + 1（数组从0开始则为n - i）
实际销量s = min(n - i + 1, m)
收益R = aᵢ × s

此时问题分解为：在n个候选单价中，选择使R最大的aᵢ。这种离散化枚举的方式保证了我们只需要检查有限个关键点。

2.2 贪心选择正确性

假设存在某个非报价数值p'能产生更大收益：

设p'介于aⱼ和aⱼ₊₁之间（aⱼ < p' < aⱼ₊₁）
此时有效买家数量与选择p = aⱼ₊₁时相同
但p' < aⱼ₊₁，因此收益p' × s ≤ aⱼ₊₁ × s

这表明我们只需要在报价集合中选取候选单价即可。用反证法可以严格证明该策略的全局最优性。

数学归纳要点：

基础情况：当n=1时，唯一报价即为最优解
归纳假设：对于n=k成立
归纳步骤：对于n=k+1，选择最大可能aᵢ不影响后续子问题的最优性

3. 算法实现与边界处理

基于上述分析，我们可以得到清晰的实现步骤：

3.1 核心算法流程

预处理阶段：
- 将报价数组升序排序
- 初始化最大收益max_profit = 0和最优单价best_price = 0

枚举阶段：

prices.sort() for i in range(len(prices)): current_price = prices[i] available = len(prices) - i sold = min(available, m) current_profit = current_price * sold # 处理多个最优解的情况 if current_profit > max_profit or (current_profit == max_profit and current_price < best_price): max_profit = current_profit best_price = current_price

输出结果：
- 返回(best_price, max_profit)

3.2 复杂度分析

操作步骤	时间复杂度	空间复杂度
排序	O(n log n)	O(1)
枚举检查	O(n)	O(1)
总计	O(n log n)	O(1)

提示：在实际编码中，可以使用语言内置的排序算法（如Python的TimSort），它们通常针对部分有序数据有优化。

3.3 关键边界条件

库存充足情况：
- 当m ≥ n时，问题简化为选择min(prices)使所有顾客都能购买
- 但根据题意仍需保证收益最大，此时应选择满足p ≤ min(prices)的最大p
多解处理技巧：
- 在比较收益时，使用严格大于判断可以自然保持第一个遇到的解
- 当需要最小单价时，改为current_price < best_price的条件判断

# 处理边界的完整代码示例 def optimal_price(prices, m): prices.sort() max_profit = best_price = 0 for i in range(len(prices)): p = prices[i] buyers = len(prices) - i sold = min(buyers, m) profit = p * sold if profit > max_profit: max_profit = profit best_price = p elif profit == max_profit and p < best_price: best_price = p return (best_price, max_profit)

4. 贪心算法的通用解题框架

通过这个案例，我们可以提炼出解决贪心类问题的通用方法论：

问题分解：
- 识别问题是否具有最优子结构
- 确认子问题的最优解能否组合成全局最优解
策略选择：
- 找出局部最优的选择标准（本例中按报价排序）
- 证明该局部选择能保证全局最优
实现优化：
- 预处理数据（排序、优先队列等）
- 设计高效的状态转移方式
边界处理：
- 明确约束条件的处理顺序
- 设计多解情况的选择策略

对比其他算法策略：

策略	适用场景	本问题适用性
贪心算法	具有贪心选择性质的问题	★★★★★
动态规划	具有重叠子问题的问题	★★☆（过度设计）
暴力枚举	解空间有限的小规模问题	★★★☆（可接受）
分治算法	可独立求解的子问题	★☆☆（不适用）