【LeetCode】 2439. Minimize Maximum of Array

Description

You are given a 0-indexed array nums comprising of n non-negative integers.
In one operation, you must:

• Choose an integer i such that 1 <= i < n and nums[i] > 0.
• Decrease nums[i] by 1.
• Increase nums[i - 1] by 1.

Return the minimum possible value of the maximum integer of nums after performing any number of operations.

Constraints:

• n == nums.length
• 2 <= n <= 105
• 0 <= nums[i] <= 109

給你一個從索引值 0 開始的陣列 nums，其包含 n 個非負整數。
每次操作，你必須：

• 選一個整數 i 其中 1 <= i < n 且 nums[i] > 0。
• 將 num[i] 減一
• 將 nums[i - 1] 加一

回傳經過任意次數的操作後，陣列 nums 中最大數值的最小可能值為何。

限制：

• n == nums.length
• 2 <= n <= 105
• 0 <= nums[i] <= 109

Example:

Example 1:

Input: nums = [3,7,1,6]
Output: 5
Explanation:
One set of optimal operations is as follows:
1. Choose i = 1, and nums becomes [4,6,1,6].
2. Choose i = 3, and nums becomes [4,6,2,5].
3. Choose i = 1, and nums becomes [5,5,2,5].
The maximum integer of nums is 5. It can be shown that the maximum number cannot be less than 5.
Therefore, we return 5.

Example 2:

Input: nums = [10,1]
Output: 10
Explanation:
It is optimal to leave nums as is, and since 10 is the maximum value, we return 10.

Solution

• 題目本身有點難理解，簡單來說你可以挑一個陣列中的數字，給他前面的數字 1
  • 自己減一，前面的加一
  • 不能給到負數
• 然後求陣列裡面的最大的數字，經過任意操作後最小可以是多少
• 可以圖像化成水位圖，水只能往前流，求水位最低
  • 灰色補到紅色的部分，最高水位為 5，因此範例測資一答案是 5

---

• 解法蠻單純的，從第零格開始計算平均水位高，留最大值作為答案
  • 第零格的平均
  • 第零格與第一格的平均
  • 第零格與第一格與第二格的平均
  • …
  • 所有格子的平均
• 數字只能往前一格傳，但因為前一格的平均已經計算過，因此也會包含在答案之內

Code

class Solution {
public:
    int minimizeArrayValue(vector<int>& nums) {
        int ans = 0;
        double sum = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            sum += nums[i];
            ans = max(ans, (int)ceil(sum / (i + 1)));
        }
        return ans;
    }
};

tags: LeetCode C++