You are given an integer array nums
of size n
.
Consider a non-empty subarray from nums
that has the maximum possible bitwise AND.
- In other words, let
k
be the maximum value of the bitwise AND of any subarray ofnums
. Then, only subarrays with a bitwise AND equal tok
should be considered.
Return the length of the longest such subarray.
The bitwise AND of an array is the bitwise AND of all the numbers in it.
A subarray is a contiguous sequence of elements within an array.
Example 1:
Input: nums = [1,2,3,3,2,2] Output: 2 Explanation: The maximum possible bitwise AND of a subarray is 3. The longest subarray with that value is [3,3], so we return 2.
Example 2:
Input: nums = [1,2,3,4] Output: 1 Explanation: The maximum possible bitwise AND of a subarray is 4. The longest subarray with that value is [4], so we return 1.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 106
Solution: Find the largest number
a & b <= a
a & b <= b
if b > a, a & b < b, we choose to start a new sequence of “b” instead of continuing with “ab”
Basically, we find the largest number in the array and count the longest sequence of it. Note, there will be some tricky cases like.
b b b b a b
b a b b b b
We need to return 4 instead of 1.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int longestSubarray(vector<int>& nums) { int ans = 0; int best = 0; for (int i = 0, l = 0; i < nums.size(); ++i) { if (nums[i] > best) { best = nums[i]; ans = l = 1; } else if (nums[i] == best) { ans = max(ans, ++l); } else { l = 0; } } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment