【脑筋急转弯】按位与最大的最长子数组【力扣第 312 场周赛】

题目

6189. 按位与最大的最长子数组

---

给你一个长度为 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

解题

方法一：脑筋急转弯

思路

根据按位与运算(&)的特性：a & b <= min(a, b) ，也就是说一个数组中任意子数组执行按位与运算后最大的结果一定是该数组中最大的值，而题目要求得到这个最大值的最长子数组长度，而要保持按位与的结果保持在最大值，只能选选取与数组中最大值相同的值来组成子数组。

那么这题就变成了：求一个数组中数组中的最大值最多连续出现了几次。

代码

class Solution {
    public int longestSubarray(int[] nums) {
        int max = 0;
        for (int num : nums) max = Math.max(num, max);
        int len = 0, maxLen = 1;
        for (int num : nums) {
            if (num == max) ++len;
            else {
                maxLen = Math.max(maxLen, len);
                len = 0;
            }
        }
        return Math.max(len, maxLen);
    }
}

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