Medium

题目描述

给你一个由非负整数组成的数组 nums。

我们定义子数组 nums[l..r]（其中 l <= r）的分数为 nums[l] AND nums[l + 1] AND ... AND nums[r]，其中 AND 是按位与运算。

考虑将数组分割成一个或多个子数组，满足以下条件：

  • 数组的每个元素恰好属于一个子数组。
  • 子数组分数的总和是最小可能值。

返回满足上述条件的分割中子数组的最大数量。

子数组是数组的一个连续部分。

示例 1：

输入：nums = [1,0,2,0,1,2]
输出：3
解释：我们可以将数组分割成以下子数组：
- [1,0]。该子数组的分数是 1 AND 0 = 0。
- [2,0]。该子数组的分数是 2 AND 0 = 0。
- [1,2]。该子数组的分数是 1 AND 2 = 0。
分数总和是 0 + 0 + 0 = 0，这是我们可以获得的最小分数。
可以证明，我们无法将数组分割成超过 3 个总分数为 0 的子数组。因此返回 3。

示例 2：

输入：nums = [5,7,1,3]
输出：1
解释：我们可以将数组分割成一个子数组：[5,7,1,3]，分数为 1，这是我们可以获得的最小分数。
可以证明，我们无法将数组分割成超过 1 个总分数为 1 的子数组。因此返回 1。

约束条件：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^6

提示：

  • 最小分数总是数组所有元素的按位与。
  • 如果最小分数不等于 0，唯一可能的分割是将所有元素保留在一个子数组中。
  • 否则，所有子数组的分数都应该为 0，我们可以贪心地分割数组，同时尽量让每个子数组尽可能小。

解题思路

这道题的关键在于理解按位与运算的性质和贪心策略。

首先分析题目要求：我们需要找到一种分割方式，使得所有子数组分数的总和最小，并在此前提下子数组数量最多。

核心观察：

  1. 整个数组所有元素的按位与结果是所有可能分割方案中分数总和的下界
  2. 如果这个下界不为0，那么无论怎么分割，分数总和都会大于这个值，所以最优策略是不分割（只有1个子数组）
  3. 如果下界为0，那么我们可以找到分割方案使得每个子数组的分数都是0，总和也是0

贪心策略： 当整个数组的按位与为0时，我们应该尽可能多地分割子数组。具体做法是：

  • 从左到右遍历数组
  • 维护当前子数组的按位与结果
  • 当按位与结果变为0时，就可以结束当前子数组，开始新的子数组
  • 这样能保证每个子数组的分数都是0，且子数组数量最多

这个贪心策略的正确性在于：按位与运算具有单调性，一旦结果为0，继续添加元素不会让结果变得更小，所以应该尽早结束当前子数组。

代码实现

class Solution {
public:
    int maxSubarrays(vector<int>& nums) {
        int total_and = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            total_and &= nums[i];
        }
        
        if (total_and != 0) {
            return 1;
        }
        
        int count = 0;
        int current_and = -1; // 初始化为全1
        
        for (int num : nums) {
            current_and &= num;
            if (current_and == 0) {
                count++;
                current_and = -1; // 重置为全1
            }
        }
        
        return count;
    }
};

class Solution:
    def maxSubarrays(self, nums: List[int]) -> int:
        total_and = nums[0]
        for i in range(1, len(nums)):
            total_and &= nums[i]
        
        if total_and != 0:
            return 1
        
        count = 0
        current_and = float('inf')  # 初始化为一个很大的数
        
        for num in nums:
            current_and &= num
            if current_and == 0:
                count += 1
                current_and = float('inf')  # 重置
        
        return count

public class Solution {
    public int MaxSubarrays(int[] nums) {
        int totalAnd = nums[0];
        for (int i = 1; i < nums.Length; i++) {
            totalAnd &= nums[i];
        }
        
        if (totalAnd != 0) {
            return 1;
        }
        
        int count = 0;
        int currentAnd = int.MaxValue;
        
        foreach (int num in nums) {
            currentAnd &= num;
            if (currentAnd == 0) {
                count++;
                currentAnd = int.MaxValue;
            }
        }
        
        return count;
    }
}

var maxSubarrays = function(nums) {
    let totalAnd = nums[0];
    for (let i = 1; i < nums.length; i++) {
        totalAnd &= nums[i];
    }
    
    if (totalAnd > 0) {
        return 1;
    }
    
    let count = 0;
    let currentAnd = nums[0];
    
    for (let i = 0; i < nums.length; i++) {
        if (i === 0) {
            currentAnd = nums[i];
        } else {
            currentAnd &= nums[i];
        }
        
        if (currentAnd === 0) {
            count++;
            if (i < nums.length - 1) {
                currentAnd = nums[i + 1];
                i++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组两次，第一次计算整体按位与，第二次执行贪心分割
空间复杂度O(1)只使用了常数个额外变量