class Solution {
public:
int minArrayLength(vector<int>& nums, int k) {
}
};
2892. 将相邻元素相乘后得到最小化数组
给定一个整数数组 nums 和一个整数 k，你可以对数组执行以下操作任意次数：
x 和 y，使得 x * y <= k ，并用一个值为 x * y 的 单个元素 替换它们（例如，在一次操作中，数组 [1, 2, 2, 3]，其中 k = 5 可以变为 [1, 4, 3] 或 [2, 2, 3]，但不能变为 [1, 2, 6]）。返回 经过任意次数的操作后， nums 的 最小 可能长度。
示例 1：
输入：nums = [2,3,3,7,3,5], k = 20 输出：3 解释：我们执行以下操作： 1. [2,3,3,7,3,5] -> [6,3,7,3,5] 2. [6,3,7,3,5] -> [18,7,3,5] 3. [18,7,3,5] -> [18,7,15] 可以证明，在执行给定操作后，最小可能长度为3.
示例 2：
输入：nums = [3,3,3,3], k = 6 输出：4 解释：由于每两个相邻元素的乘积都大于 6，所以无法执行任何操作。因此，答案为 4。
约束条件：
1 <= nums.length <= 1050 <= nums[i] <= 1091 <= k <= 109原站题解
python3 解法, 执行用时: 88 ms, 内存消耗: 27.5 MB, 提交时间: 2023-10-21 20:19:52
class Solution:
def minArrayLength(self, nums: List[int], k: int) -> int:
if 0 in nums: return 1
res, sm = 0, k + 1
for i in nums:
if sm * i > k: sm, res = i, res + 1
else: sm *= i
return res
java 解法, 执行用时: 2 ms, 内存消耗: 54.8 MB, 提交时间: 2023-10-21 20:19:39
class Solution {
public int minArrayLength(int[] nums, int k) {
for(int x:nums)
if(x == 0) return 1;
int n = nums.length, count = n;
long product = nums[0];
for(int i = 1; i < n; ++i){
int x = nums[i];
product *= x;
if(product <= k)
--count;
else
product = x;
}
return count;
}
}