🌕🌕 330. 按要求补齐数组

难度: 🌕🌕

问题描述

---

解法

class Solution {
    public int minPatches(int[] nums, int n) {
        // 思路：
        // 找规律
        // 假设 [1, x] 是连续的，那么通过 [1, x] 可以得到 [1 + x, x + x - 1] --> [1 + x, 2x - 1]
        // 即只要有 [1, x] 连续区间，无需添加任何值，即可扩展到 [1, 2x - 1] 连续
        // 假设数组中存在一个 val ∈ (1, 2x - 1) 那么，覆盖连续区间可扩展到 [1, 2x - 1 + val]
        // 例 nums[1, 5, 10], n = 20
        // 初始化 max = 0, index = 0, res = 0
        // 1) max + 1 == nums[index] = 1 ==> max += max + 1, index ++
        // ==> max = 1, index = 2
        // 2) max + 1 = 2 < nums[index] = 5 ==> max += max + 1, res ++[需要增加 max + 1 这个数]
        // ==> max = 3, index = 2
        // 3) max + 1 = 4 < nums[indes] = 5 ==> max += max + 1, res ++
        // ==> max = 7, index = 2
        // 4) max + 1 = 8 > nums[index] = 5 ==> max += nums[index], index ++ 
        // 本身能到达 [1, 7] 现在额外多了个助力 5，∴ 变得更加强大，能到达 [1, 12]
        // ==> max = 12, index = 3
        // 5) max + 1 = 13 > nums[index] = 10 ==> max += nums[index], index ++
        // ==> max = 23, index = 4 退出

        int len = nums.length;
        long max = 0; // 防止超范
        int index = 0;
        int res = 0; // 要添加的数字个数

        while(max < n) {
            long exp = max + 1; // 想要的下一个连续值
            if(index < len && exp == nums[index]) {
                // 存在想要的下一个连续值
                index ++;
                max += exp; // 更新能到达的最远值
            } else if(index < len && exp < nums[index]) {
                // 不存在想要的下一个连续值
                res ++; // 添加节点
                max += exp;
            } else if(index < len && exp > nums[index]) {
                // 有新的助力，最远距离进一步扩大
                max += nums[index];
                index ++; // 助力只能使用一次
            } else if(index >= len) {
                // 后续已经没有任何助力，如果进入到这一步，说明肯定需要添加新节点
                res ++;
                max += exp;
            }
        }
        return res;
    }
}

---

输出