一种削峰算法

削峰算法，故名思义，就是将峰值高的地方铲掉。

加入有九座山，高度分别是 [9,8,7,6,5,4,3,2,1]；削掉峰值的总和是k，怎样可以尽可能的削减高峰。

按照常规逻辑，每次将最高的减少一米，然后山峰重新排序，接着再将最高的削减一米，直到k次使用完。
按照这种思路，可以使用大顶堆来解决，每次将最大值取出来减一之后再塞回去

while (!que.empty() && k--) {
    int tmp = que.top();
    que.pop();
    if (tmp > 0) {
        tmp--;
        que.push(tmp);
    }
}

但是这种操作在大用例集下会超时，因为是一个一个操作。
有没有一种办法，可以直接算出削峰之后的平均线，然后所有高出这个平均线的都一把削掉，而不是一米一米的削掉呢？

// 通过二分法找到平均线
int left = 0;
int right = 100010;
while (left < right) {
    int mid = (left + right) / 2;
    long long tmp = 0;
    for (int i = 0; i < n; i++) {
        if (data[i] > mid) {
            tmp += data[i] - mid;
        } 
    }
    if (tmp > k) {
        left =mid + 1;
    } else {
        right = mid;
    }

}
int target = left;  //确定了平均线为target

int x = 0;

// 削掉高于平均线的山峰
for (int i = 0; i < n; i++) {
    if (data[i] > target) {
        x += data[i] - target;
        data[i] = target;
    }
}
// 所有高于平均线的山峰削掉之后 k仍有富裕，但是k剩余值不够再降一次平均线
int y = k - x;  

for (int i = 0; i < n; i++) {  // 将剩余的k 平摊到每一座高峰上
    if (y != 0 && data[i] > 0) {
        data[i]--;
        y--;
    }
}

leetcode对应练习题

最后

以上就是火星上睫毛为你收集整理的一种削峰算法的全部内容，希望文章能够帮你解决一种削峰算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。