leetcode 330. Patching Array | 1798. Maximum Number of Consecutive Values You Can Make

向右看齐 2022-09-09 06:48 130阅读 0赞

## 1798. Maximum Number of Consecutive Values You Can Make | 1798. 你能构造出连续值的最大数目 ##

[https://leetcode.com/problems/maximum-number-of-consecutive-values-you-can-make/][https_leetcode.com_problems_maximum-number-of-consecutive-values-you-can-make]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

这题没有套路。。

随手就是一个 O(2^n) 暴力，妥妥的超时了。看了 hint 没看懂，后来看了答案：

参考：[https://leetcode-cn.com/problems/maximum-number-of-consecutive-values-you-can-make/solution/ni-neng-gou-zao-chu-lian-xu-zhi-de-zui-d-hlxf/][https_leetcode-cn.com_problems_maximum-number-of-consecutive-values-you-can-make_solution_ni-neng-gou-zao-chu-lian-xu-zhi-de-zui-d-hlxf]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Solution { 
        public int getMaximumConsecutive(int[] coins) { 
            Arrays.sort(coins);
            int end = 0;
            for (int coin : coins) { 
                if (coin <= end + 1) end += coin;
                else break;
            }
            return end + 1;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]

--------------------

## leetcode 330. Patching Array | 330. 按要求补齐数组 ##

[https://leetcode.com/problems/patching-array/][https_leetcode.com_problems_patching-array]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 3]

## 题解 ##

做过上一道 **330. Patching Array** 之后，这个题的思路就简单了。

当连续区间 0~end 和下一个 num 不连续的时候，用 end+1 来填充，然后更新 end，直到 end 能和下一个 num 毗邻为止。

class Solution { 
        public int minPatches(int[] nums, int n) { 
            int count = 0;
            long end = 0;
            for (long num : nums) { 
                while (num > end + 1) { 
                    count += 1;
                    end += (end + 1);
                    if (end >= n) return count; // 满足条件，随时跑路！
                }
                end += num;
                if (end >= n) return count;  // 满足条件，随时跑路！
            }
            // 收尾
            while (n > end + 1) { 
                count += 1;
                end += (end + 1);
            }
            return count;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 4]

[https_leetcode.com_problems_maximum-number-of-consecutive-values-you-can-make]: https://leetcode.com/problems/maximum-number-of-consecutive-values-you-can-make/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/0cc2ce7c586e4963b7af0c25d94b5e65.png
[https_leetcode-cn.com_problems_maximum-number-of-consecutive-values-you-can-make_solution_ni-neng-gou-zao-chu-lian-xu-zhi-de-zui-d-hlxf]: https://leetcode-cn.com/problems/maximum-number-of-consecutive-values-you-can-make/solution/ni-neng-gou-zao-chu-lian-xu-zhi-de-zui-d-hlxf/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/2be761fc756e460589663e6a761b7b82.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/3e198278dd8c4f31aa9241bfad6ebcf2.png
[https_leetcode.com_problems_patching-array]: https://leetcode.com/problems/patching-array/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/6a318f79f8b64308872e169894527067.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220829/c753345af2b14692a814c10cc4e07a80.png