题目分析

这是第217场周赛的第四题，这次周赛的难度较大，都是有关数组和数学的题目，重在考察小伙伴们对数据结构的掌握程度。

堆

这个题目的特点是偶数可以除以2，奇数可以乘2，因此数组中的值是有上限的，上限就是全部变成偶数。因此我们可以先将数组变大，然后求出最大值和最小值之间的差距。然后看最大值能否变小，如果可以，说明最大最小值之间的差异就会变小。

因此我们可以维护一个最大堆，我们动态维护这个堆的最大值和最小值即可。维护最大值不需要我们手动维护，但是维护最小值应该如何操作呢？

只需要将最大值除以2以后和最小值比较，看一看是否需要更新最小值。再将更新后的最大值放入堆中即可。

堆操作的时间复杂度为$O(nlog(n))$，每个数最多需要插入$log(nums[i])$次，因此算法的**时间复杂度为$O(nlog(n)log(a_i))$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>
#include<queue>

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        priority_queue<int> q;
        int mini = nums[0] * 2;
        for (int x : nums) {
            int tmp = x & 1 ? x * 2 : x;
            q.push(tmp);
            mini = min(mini, tmp);
        }
        int res = q.top() - mini;
        while ((q.top() & 1) == 0) {
            int maxi = q.top() / 2;
            q.pop();
            q.push(maxi);
            mini = min(mini, maxi);
            res = min(res, q.top() - mini);
        }
        return res;
    }
};

刷题总结

堆是一种非常重要的数据结构，在刷题中常常会遇到，在动态维护最值时有重要应用，小伙伴们要加强这方面的训练。