📶連綿不斷 擁有最大AND值的子陣列長度_Longest Subarray With Max AND_LC #2419

Pietro De Grandi on Unsplash

題目敘述 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)。

Reference

[1] Longest Subarray With Maximum Bitwise AND - LeetCode