LeetCode 1648. 销售价值减少的颜色球

Categories:

题目描述
思路分析
1. 解法一：贪心 + 二分查找（推荐）
2. 解法二：贪心 + 排序模拟
相似题目

题目描述

✅ 1648. 销售价值减少的颜色球

思路分析

解法一：贪心 + 二分查找（推荐）

核心思路：

每次应优先卖出当前数量最多的颜色球，使收益最大化

将库存数组降序排序，每次从最大值开始填平：找到一个”水平线” mid，使得所有高于 mid 的球先被卖完

二分查找满足条件的水平线：即前 k 大的总球数 >= orders

整批水平线以上的球按等差数列求和，剩余部分单独补充

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示颜色数量，排序 O(n log n)，二分 O(n log n)

空间复杂度：O(log n)，排序递归栈空间

class Solution {

  private static final int MOD = 1_000_000_007;

  public int maxProfit(int[] inventory, int orders) {
    Arrays.sort(inventory);
    int n = inventory.length;

    // 反转为降序
    for (int i = 0; i < n / 2; i++) {
      int tmp = inventory[i];
      inventory[i] = inventory[n - 1 - i];
      inventory[n - 1 - i] = tmp;
    }

    // 二分查找水平线 mid
    int lo = 0, hi = inventory[0];
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      // 计算所有高于 mid 的球数量总和
      long count = 0;
      for (int v : inventory) {
        if (v > mid) {
          count += v - mid;
        }
      }
      if (count <= orders) {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }

    // lo 即为水平线
    int mid = lo;
    long ans = 0;
    long remainOrders = orders;

    for (int v : inventory) {
      if (v > mid) {
        // 等差数列：从 v 到 (mid+1)
        long cnt = v - mid;
        ans = (ans + (long) (v + mid + 1) % MOD * cnt % MOD * 499122177 % MOD) % MOD;
        remainOrders -= cnt;
      }
    }

    // 剩余订单全以 mid 价格卖出
    ans = (ans + remainOrders % MOD * mid % MOD) % MOD;

    return (int) ans;
  }
}

func maxProfit(inventory []int, orders int) int {
    const mod = 1_000_000_007

    sort.Sort(sort.Reverse(sort.IntSlice(inventory)))

    // 二分查找水平线
    lo, hi := 0, inventory[0]
    for lo < hi {
        mid := lo + (hi-lo)/2
        count := 0
        for _, v := range inventory {
            if v > mid {
                count += v - mid
            }
        }
        if count <= orders {
            hi = mid
        } else {
            lo = mid + 1
        }
    }

    mid := lo
    ans := 0
    remain := orders

    for _, v := range inventory {
        if v > mid {
            cnt := v - mid
            // 等差数列求和：(v + mid+1) * cnt / 2
            ans = (ans + (v+mid+1)%mod*cnt%mod*500000004%mod) % mod
            remain -= cnt
        }
    }

    // 剩余订单按 mid 价格
    ans = (ans + remain%mod*mid%mod) % mod

    return ans
}

解法二：贪心 + 排序模拟

核心思路：

排序后逐层”削平”：每次将最高层的所有球卖出，直到订单耗尽

维护当前最高值 cur 和下一层高度 next，一批次批量计算

利用等差数列公式累加收益，避免逐个遍历

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示颜色数量

空间复杂度：O(log n)，排序栈空间

class Solution {

  private static final int MOD = 1_000_000_007;

  public int maxProfit(int[] inventory, int orders) {
    Arrays.sort(inventory);
    int n = inventory.length;
    long ans = 0;
    long cnt = 1;

    // 从最大值开始逐层削平
    for (int i = n - 1; i >= 0 && orders > 0; i--) {
      int next = (i > 0) ? inventory[i - 1] : 0;
      // 当前层高度差
      long diff = inventory[i] - next;
      long total = diff * cnt;

      if (total <= orders) {
        // 整批卖出当前层，使用等差数列求和
        long hi = inventory[i], lo = next + 1;
        ans = (ans + (hi + lo) % MOD * diff % MOD * cnt % MOD * 499122177 % MOD) % MOD;
        orders -= total;
      } else {
        // 部分卖出
        long full = orders / cnt;
        long rem = orders % cnt;
        long hi = inventory[i], lo = inventory[i] - full + 1;
        if (full > 0) {
          ans = (ans + (hi + lo) % MOD * full % MOD * cnt % MOD * 499122177 % MOD) % MOD;
        }
        ans = (ans + rem % MOD * (inventory[i] - full) % MOD) % MOD;
        orders = 0;
      }
      cnt++;
    }

    return (int) ans;
  }
}

func maxProfit(inventory []int, orders int) int {
    const mod = 1_000_000_007

    sort.Ints(inventory)
    n := len(inventory)
    ans := 0
    cnt := 1

    for i := n - 1; i >= 0 && orders > 0; i-- {
        next := 0
        if i > 0 {
            next = inventory[i-1]
        }
        diff := inventory[i] - next
        total := diff * cnt

        if total <= orders {
            hi, lo := inventory[i], next+1
            // 等差数列求和
            ans = (ans + (hi+lo)%mod*diff%mod*cnt%mod*500000004%mod) % mod
            orders -= total
        } else {
            full := orders / cnt
            rem := orders % cnt
            hi, lo := inventory[i], inventory[i]-full+1
            if full > 0 {
                ans = (ans + (hi+lo)%mod*full%mod*cnt%mod*500000004%mod) % mod
            }
            ans = (ans + rem%mod*(inventory[i]-full)%mod) % mod
            orders = 0
        }
        cnt++
    }

    return ans
}

相似题目

题目	难度	考察点
1552. 两球之间的磁力	中等	二分查找、贪心
875. 爱吃香蕉的珂珂	中等	二分查找
1011. 在 D 天内送达包裹的能力	中等	二分查找
410. 分割数组的最大值	困难	二分查找、动态规划
786. 第 K 个最小的素数分数	中等	二分查找、堆
373. 查找和最小的 K 对数字	中等	堆、贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/64943900