2439. 最小化数组中的最大值

题目链接：

看到“最小化最大值”想到二分答案。我们猜测一个上界 \(\rm limit\)，\(\rm limit\) 越大越符合条件，越小越不易符合条件，满足单调性。由于当前维护的是数组经过操作是否满足最大值为 \(\rm limit\)，可以从后往前遍历，遇到比 \(\rm limit\) 大的就把大的那部分减去加到前一个元素上。遍历结束后看第一个元素，若 \(\rm \leqslant limit\) 就满足，否则说明最大值不是 \(\rm limit\)。

在 \(\rm [0,max]\) 上二分，其中 \(\rm max\) 是数组元素的最大值。

class Solution {
public:
    bool check(int limit, vector<int>& nums) {
        int n = nums.size();
        vector<long long> t;//需要long long，否则 t[i-1] 增加时有可能溢出
        t.assign(nums.begin(), nums.end());//复制原数组，防止引用修改原数组，导致下次二分时数组发生改变
        for (int i = n - 1; i > 0; i--) {
            if (t[i] > limit) {
                t[i - 1] += t[i] - limit;
            }
        }
        return t[0] <= limit;
    }

    int minimizeArrayValue(vector<int>& nums) {
        int l = 0, r = *max_element(nums.begin(), nums.end()) + 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid, nums)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

如要在 \(O(1)\) 的空间上操作，可以选择维护一个 \(\rm extra\) 变量，用于记录当前元素比 \(\rm limit\) 大的部分。

class Solution {
public:
    bool check(int limit, vector<int>& nums) {
        int n = nums.size();
        long long extra = 0;
        for (int i = n - 1; i > 0; i--) {
            long long t = nums[i] + extra;
            if (t > limit) {
                extra = t - limit;
            } else extra = 0;
        }
        return nums[0] + extra <= limit;
    }

    int minimizeArrayValue(vector<int>& nums) {
        int l = 0, r = *max_element(nums.begin(), nums.end()) + 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid, nums)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};