Leetcode2528. 最大化城市的最小电量

本文主要是介绍Leetcode2528. 最大化城市的最小电量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Every day a Leetcode

题目来源：2528. 最大化城市的最小电量

解法1：二分查找 + 前缀和 + 差分数组

看到「最大化最小值」或者「最小化最大值」就要想到二分答案，这是一个固定的套路。

为什么？一般来说，二分的值越大，越能/不能满足要求；二分的值越小，越不能/能满足要求，有单调性，可以二分。

二分答案 minPower，从左到右遍历 stations，如果 stations[i] 电量不足 minPower，那么需要建供电站来补足。

在哪建供电站最好呢？

由于 i 左侧的不需要补足，所以贪心地在 min⁡(i+r,n−1) 处建是最合适的，恰好让 i 在覆盖范围的边界上。

设需要建 m 个供电站，那么需要把 [i,min⁡(i+2r,n−1)] 范围内的电量都增加 m。

方法很多，用差分数组来更新是最简单的。

最后判断修建的供电站是否超过 k，如果超过说明 minPower 偏大，否则说明偏小。

代码：

/** @lc app=leetcode.cn id=2528 lang=cpp** [2528] 最大化城市的最小电量*/// @lc code=start
class Solution
{
public:long long maxPower(vector<int> &stations, int r, int k){int n = stations.size();vector<long long> preSum(n + 1, 0);long long diff[n];vector<long long> power(n, 0);// 求前缀和for (int i = 1; i <= n; i++)preSum[i] = preSum[i - 1] + stations[i - 1];// 求电量for (int i = 0; i < n; ++i)power[i] = preSum[min(i + r + 1, n)] - preSum[max(i - r, 0)];auto check = [&](long long min_power) -> bool{memset(diff, 0, sizeof(diff)); // 重置差分数组long long sum_d = 0, need = 0;for (int i = 0; i < n; i++){sum_d += diff[i]; // 累加差分值long long m = min_power - power[i] - sum_d;if (m > 0){ // 需要 m 个供电站need += m;if (need > k)return false; // 提前退出这样快一些sum_d += m;       // 差分更新if (i + r * 2 + 1 < n)diff[i + r * 2 + 1] -= m; // 差分更新}}return true;};// 二分查找，开区间写法long long left = *min_element(power.begin(), power.end());long long right = left + k + 1;while (left + 1 < right){long long mid = left + (right - left) / 2;if (check(mid))left = mid;elseright = mid;}return left;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(nlogk)，其中 n 为数组 stations 的长度。二分需要循环 O(log⁡k) 次。

空间复杂度：O(n)，其中 n 为数组 stations 的长度。

这篇关于Leetcode2528. 最大化城市的最小电量的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---