题目描述
给你一个长度为 n
的整数数组 nums
。
考虑 nums
中进行 按位与(bitwise AND)运算得到的值 最大 的 非空 子数组。
- 换句话说,令
k
是nums
任意 子数组执行按位与运算所能得到的最大值。那么,只需要考虑那些执行一次按位与运算后等于k
的子数组。
返回满足要求的 最长 子数组的长度。
数组的按位与就是对数组中的所有数字进行按位与运算。
子数组 是数组中的一个连续元素序列。
样例
输入:nums = [1,2,3,3,2,2]
输出:2
解释:
子数组按位与运算的最大值是 3。
能得到此结果的最长子数组是 [3,3],所以返回 2。
输入:nums = [1,2,3,4]
输出:1
解释:
子数组按位与运算的最大值是 4。
能得到此结果的最长子数组是 [4],所以返回 1。
限制
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
算法
(思维题) $O(n)$
- 由于两个数字的 按位与 运算不会超过两个数字的最小值,所以运算能得到的最大值一定是数组中数字的最大值。
- 所以答案就是数组中最大值的最长连续子数组的长度。
时间复杂度
- 遍历数组两次,时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int longestSubarray(vector<int>& nums) {
const int n = nums.size();
int ma = nums[0];
for (int i = 0; i < n; i++)
ma = max(ma, nums[i]);
int c = 0, ans = 0;
for (int i = 0; i < n; i++) {
if (nums[i] == ma) c++;
else c = 0;
ans = max(ans, c);
}
return ans;
}
};