Medium

题目描述

给你一个长度为 n 的整数数组 nums。

考虑 nums 中进行按位与（AND）运算得到的值最大的 非空 子数组。

  • 换句话说，令 k 是 nums 任意 子数组执行按位与运算所能得到的最大值。那么，只需要考虑那些执行按位与运算后等于 k 的子数组。

返回满足要求的 最长 子数组的长度。

数组的按位与就是对数组中的所有数字进行按位与运算。

子数组 是数组中的一个连续元素序列。

示例 1：

输入：nums = [1,2,3,3,2,2]
输出：2
解释：
子数组按位与运算的最大值是 3。
能得到此结果的最长子数组是 [3,3]，长度为 2。

示例 2：

输入：nums = [1,2,3,4]
输出：1
解释：
子数组按位与运算的最大值是 4。
能得到此结果的最长子数组是 [4]，长度为 1。

提示：

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

解题思路

这道题的关键洞察是：按位与运算只会让结果变小或保持不变，不会变大。

当我们对两个不同的数进行按位与运算时，结果总是严格小于这两个数的最大值。这意味着，要想得到最大的按位与值，子数组中的所有元素必须完全相同。

基于这个观察，我们可以得出结论：

  1. 最大按位与值就是数组中的最大元素值
  2. 我们需要找到由连续相同最大元素组成的最长子数组

解题步骤：

  1. 首先找到数组中的最大值
  2. 遍历数组，找到所有由连续最大值组成的子数组
  3. 返回这些子数组中的最大长度

这个方法的时间复杂度是 O(n)，空间复杂度是 O(1)，非常高效。我们只需要两次遍历：第一次找最大值，第二次找最长连续序列。

代码实现

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int maxVal = *max_element(nums.begin(), nums.end());
        int maxLen = 0, currentLen = 0;
        
        for (int num : nums) {
            if (num == maxVal) {
                currentLen++;
                maxLen = max(maxLen, currentLen);
            } else {
                currentLen = 0;
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        max_val = max(nums)
        max_len = 0
        current_len = 0
        
        for num in nums:
            if num == max_val:
                current_len += 1
                max_len = max(max_len, current_len)
            else:
                current_len = 0
        
        return max_len

public class Solution {
    public int LongestSubarray(int[] nums) {
        int maxVal = nums.Max();
        int maxLen = 0, currentLen = 0;
        
        foreach (int num in nums) {
            if (num == maxVal) {
                currentLen++;
                maxLen = Math.Max(maxLen, currentLen);
            } else {
                currentLen = 0;
            }
        }
        
        return maxLen;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSubarray = function(nums) {
    const maxVal = Math.max(...nums);
    let maxLength = 0;
    let currentLength = 0;
    
    for (let num of nums) {
        if (num === maxVal) {
            currentLength++;
            maxLength = Math.max(maxLength, currentLength);
        } else {
            currentLength = 0;
        }
    }
    
    return maxLength;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)需要两次遍历数组：一次找最大值，一次找最长连续序列
空间复杂度O(1)只使用常数额外空间存储变量

相关题目