題目

Leetcode 2024/09/14 Daily
2419. Longest Subarray With Maximum Bitwise AND
難度: 中等偏易

題意

給定一整數陣列nums，求最長的子陣列的長度，使得所有子陣列元素AND值最大。

方向

Naive法: 用雙指標(Two pointer)造出所有的子陣列，再一個個把元素AND起來；複雜度為O(N^3)。

觀察題目給的輸入限制，輸入的長度為10^5。
根據經驗，五次方的輸入要在O(N)時間內做完才能AC。

再觀察題目給的範例，發現使子陣列元素AND值最大，其實就是子陣列的元素都必須是原陣列的最大值。
因為AND的特性，兩數互相AND，BIT為1的數量只能越來越少，其值也會越來越小。
也就是A & B <= min(A, B)

因此此題先first pass，求出最大值；再second pass求出元素皆為最大值的最長子陣列。

實作

class Solution
{
public:
    int longestSubarray(vector<int> &nums)
    {
        int n = (int)nums.size();
        int maximum = *max_element(nums.begin(), nums.end());

        int res = 0;   // Size of subarray
        int left = -1; // Last begin index of consecutive maximum subarray
        for (int i = 0; i < n; i++)
        {
            if (nums[i] == maximum && left == -1)
                left = i;
            else if (nums[i] != maximum && left != -1)
            {
                res = max(res, i - left);
                left = -1;
            }
        }
        if (left != -1)
            res = max(res, n - left);

        return res;
    }
};

分析

時間複雜度: O(N)，two pass
空間複雜度: O(1)

結果