題目敘述 2419. Longest Subarray With Maximum Bitwise AND
給定一個輸入陣列nums，請找出擁有最大bitwise AND值的子陣列長度是多少?
測試範例
Example 1:Input: nums = [1,2,3,3,2,2]
Output: 2
Explanation:
[3,3]的AND值最大，子陣列長度為2。
Example 2:
Input: nums = [1,2,3,4]
Output: 1
Explanation:
[4]的AND值最大，子陣列長度為1。
約束條件
Constraints:
1 <= nums.length <= 10^5
輸入陣列nums的長度介於1~十萬之間。
1 <= nums[i] <= 10^6
每個陣列元素值介於1~一百萬之間。
演算法 根據AND特質去延伸最大值的連續區間
bitwise AND值如果要維持，
那就必須每個bit都相同，可以推出區間內的值都必須相同。
如果要得到bitwise AND最大值，那麼本身就必須是陣列最大值。
舉個例子幫助理解，例如 999 AND 999 肯定大於 888 AND 888。
程式碼 根據AND特質去延伸最大值的連續區間
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
# Find the largest number in nums.
max_val = 0
# Length of subarray which has max bitwise AND value
best_length = 0
# Count the length of the continues subarray that only contains MAX
counter = 0
for number in nums:
if number == max_val:
# If the current number is MAX, increase counter
counter +=1
# update best length of subarray which has max bitwise AND value
best_length = max(best_length, counter)
elif number > max_val:
# update max value
max_val = number
# reset best length and counter as 1
best_length, counter = 1, 1
else:
# Otherwise, reset count.
counter = 0
return best_length
複雜度分析
時間複雜度: O(n)
線性掃描每個元素值，計算擁有最大AND值區間的子陣列長度。
空間複雜度: O(1)
所用到的都是固定尺寸的臨時變數，所需空間為O(1)。
