题目

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

考虑 nums 中进行 按位与（bitwise 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

解题思路

问题分析

第一步：确定最大按位与结果 (k)

这一步是整个解法的基石。我们需要利用“按位与”运算的一个关键性质：

性质： 对于任意两个非负整数 A 和 B，A & B <= min(A, B)。 也就是说，两个数按位与的结果，永远不会大于其中较小的那个数。

我们可以将这个性质推广到一个数组：一个数组中所有元素的按位与结果，必然小于或等于数组中的任何一个元素。

推论： 对于 nums 数组中的任意一个子数组，其按位与的结果绝对不可能大于该子数组中的任何一个元素。因此，它也绝对不可能大于整个 nums 数组中的最大值。

让我们来举个例子：nums = [1, 2, 3, 4]

• 子数组 [2, 3] 的按位与是 2 & 3 = 2。 2 小于等于 min(2, 3)。
• 子数组 [1, 2, 3, 4] 的按位与是 1 & 2 & 3 & 4 = 0。 0 小于等于 1, 2, 3, 4 中的任何一个。

所以，我们可以得出结论： 所有子数组的按位与结果中，可能出现的最大值 (k)，就是 nums 数组本身的最大值 max(nums)。

1. 我们已经证明了，按位与的结果不可能超过 max(nums)。
2. 我们总能找到一个子数组，其按位与的结果恰好等于 max(nums)。这个子数组就是 [max(nums)] 本身（一个只包含最大值的子数组）。

因此，问题的第一部分解决了：我们要找的那个最大的按位与结果 k，就是 max(nums)。

第二步：寻找满足条件的最长子数组

现在问题被大大简化了。我们已经知道了目标 k = max(nums)。 我们需要寻找一个最长的子数组，使得其所有元素的按位与结果等于 k。

我们再回顾一下那个性质：A & B & C ... <= min(A, B, C, ...)。 假设我们有一个子数组 sub，它的按位与结果是 k。 AND(sub) = k

这意味着子数组 sub 中的每一个元素都必须大于或等于 k。 sub[i] >= k for all i in sub

但是我们又知道，k 已经是整个 nums 数组的最大值了。所以，子数组 sub 中不可能有任何元素大于 k。

结合这两点，唯一的可能性就是： 子数组 sub 中的每一个元素都必须等于 k。

• 如果子数组中有一个元素 x < k，那么整个子数组的按位与结果就会 < k。
• 如果子数组中所有元素都等于 k，例如 [k, k, k]，那么 k & k & k = k，满足条件。

所以，问题再次被简化： 我们要找的，其实就是原数组中由最大值 k 组成的连续子数组的最长长度。

解题思路

连续子数组可以在一次遍历得出，只要随时更新最大值，并在这个最大值的基础上记录最长长度，如果找到了更新的最大值，及时抛弃旧的记录。

具体代码

class Solution {
public:

    int maxmium;
    int count;
    int result;
    int now;
    int next;

    int longestSubarray(vector<int>& nums) {

        maxmium = nums[0]; result = 1; count = 1;

        for(auto it = nums.begin(); it < (nums.end() - 1); it++)
        {
            now = *it;
            next = *(it + 1);

            if(next != now)
            {
                if(next > now)
                {
                    if(next > maxmium)
                    {
                        maxmium = next;
                        result = 1;
                    }
                }
                count = 1;
            }
            else if(now == maxmium)
            {
                count++;
                result = max(result, count);
            }
            
        }
        return result;
        
    }
};