(每日一题) 力扣 2208 将数组和减半的最少操作次数

🌟 LeetCode 2208. 将数组和减半的最少操作次数：贪心策略与大根堆的完美结合

🔍 问题描述

给定一个正整数数组 nums ，每次操作可以选择任意一个元素将其减半（可对同一元素多次操作）。要求找到使数组总和 至少减少一半 所需的 最少操作次数 。

示例分析

以示例 nums = [5,19,8,1] 为例：

• 初始总和 ：33 → 目标减少量 ：16.5
• 操作路径 ：19→9.5→4.75、8→4
• 最终总和 ：14.75（减少量18.25 ≥ 16.5）
• 最少操作次数 ：3

💡 算法思路

1. 贪心策略的选择

每次选择当前数组中的 最大值 进行减半操作，这是最优策略的数学基础：

• 交换论证法 ：假设某次未选最大值而选较小值，后续操作需补偿更多次数。例如，若未减半最大值 x 而选较小值 y ，后续仍需处理 x ，总操作次数必然更多。
• 直观理解 ：最大值贡献的减少量最大（ x/2 ），优先处理能最快逼近目标。

2. 大根堆的运用

直接遍历数组找最大值的时间复杂度为 O(n²)，会超时（如 n=1e5 时）。使用**优先队列（大根堆）**优化：

• 堆特性 ：取最大值 O(1)，插入 O(log n)。
• 动态维护 ：每次减半后重新插入堆，保持堆的有效性。

是

否

初始数组

构建大根堆

当前总和 > 目标值?

取堆顶元素减半

更新总和并重新入堆

返回操作次数

🛠 代码实现解析

class Solution {
public:
    int halveArray(vector<int>& nums) {
        priority_queue<double> maxHeap;  // 大根堆存储元素
        double sum = 0;
        
        // 初始化堆并计算总和（时间复杂度O(n)）
        for (auto& e : nums) {
            maxHeap.push(e);
            sum += e;
        }

        int ret = 0;
        double target = sum / 2;  // 需减少的总量
        
        while (sum > target) {     // 循环直到满足条件
            double top = maxHeap.top(); 
            maxHeap.pop();
            
            double half = top / 2; // 减半操作
            sum -= half;           // 更新当前总和
            maxHeap.push(half);    // 重新入堆（维护堆结构）
            
            ++ret;                 // 操作计数
        }
        return ret;
    }
};

关键代码说明：

1. 堆初始化 （网页4、网页10）：

   • 遍历数组压入堆 → 自动构建大根堆 。
   • 计算初始总和 sum → 用于确定目标减少量。

2. 循环处理 ：

   • 取堆顶 ：当前最大值（O(1)）。
   • 减半并更新总和 ：实际减少量为 top/2 （原值贡献的减少量为 top - top/2 ）。
   • 重新入堆 ：保持堆结构，确保下次操作仍取最大值。

⏳ 复杂度分析

• 时间复杂度 ：O(n log n)
  • 建堆 ：O(n)（利用 priority_queue 的构造函数优化）。
  • 堆操作 ：每次取最大值和插入为 O(log n)，最多操作 n 次（极端情况所有元素多次减半）。
• 空间复杂度 ：O(n)
  • 堆存储所有元素（最坏情况存储 n 个元素）。