具有最大位與的最長子數組

2419。具有最大位元與

的最長子數組

難度：中

主題：陣列、位元操作、腦筋急轉彎

給你一個大小為 n 的整數陣列 nums。

考慮 nums 中的一個非空子數組，它具有最大可能的按位與。

• 換句話說，令 k 為 任意 nums 子數組位與的最大值。然後，只應考慮位元與等於 k 的子數組。

回傳最長這樣的子數組的長度。

陣列的位元與為陣列中所有數字的位元與。

子數組是數組中連續的元素序列。

範例1：

• 輸入： nums = [1,2,3,3,2,2]
• 輸出： 2
• 說明：
  • 子數組的最大可能位元與為 3。
  • 具有該值的最長子數組是 [3,3]，因此我們傳回 2。

範例2：

• 輸入： nums = [1,2,3,4]
• 輸出： 1
• 說明：
  • 子數組的最大可能位元與為 4。
  • 具有該值的最長子數組是 [4]，因此我們傳回 1。

約束：

• 1 1
• 1 6

提示：

1. 請注意，兩個不同數字的位元與將始終嚴格小於這兩個數字的最大值。
2. 這告訴我們我們應該選擇的子數組的性質是什麼？

解：

我們先一步步分解問題：

主要見解：

1. 位元與屬性:

   • 兩個數字的位元與通常小於或等於兩個數字。
   • 因此，如果我們在陣列中找到最大值，則實現該最大位元與值的子陣列必須由該最大值重複組成。

2. 目標：

   • 找出數組中的最大值。
   • 找到該最大值的最長連續子數組，因為子數組中的任何其他數字都會減少整體位元與結果。

計劃：

1. 遍歷數組並確定最大值。
2. 再次遍歷數組，找出所有元素都等於該最大值的最長連續子數組。

例子：

對於輸入數組 [1,2,3,3,2,2]，最大值為 3。只有 3s 的最長連續子數組是 [3,3]，長度為 2。

讓我們用 PHP 實作這個解：2419。具有最大位元組與
的最長子數組

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function longestSubarray($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$nums1 = [1, 2, 3, 3, 2, 2];
$nums2 = [1, 2, 3, 4];

echo "Output for [1, 2, 3, 3, 2, 2]: " . longestSubarray($nums1) . "\n"; // Output: 2
echo "Output for [1, 2, 3, 4]: " . longestSubarray($nums2) . "\n";       // Output: 1
?>

解釋：

1. 第 1 步：我們先使用 PHP 內建的 max() 函數來找出陣列中的最大值。
2. 第2步：我們初始化兩個變量，$maxLength用於儲存最長子數組的長度，$currentLength用於追蹤最大值的當前連續子數組的長度。
3. 第 3 步：我們迭代數組：
   • 如果目前數字等於最大值，我們將增加目前子數組的長度。
   • 如果目前數字不等於最大值，我們檢查目前子數組是否是迄今為止最長的並重置長度。
4. 最後一步：循環之後，我們確保如果最長的子數組位於數組末尾，我們仍然考慮它。
5. 最後，我們傳回僅包含最大值的最長子陣列的長度。

時間複雜度：

• 找出最大值需要 (O(n))。
• 遍歷數組找到最長的子數組需要 (O(n))。
• 總體時間複雜度：(O(n))，其中 (n) 是陣列的長度。

測試用例：

對於輸入 [1, 2, 3, 3, 2, 2]，輸出為 2，對於 [1, 2, 3, 4]，輸出為 1，如預期。

這個解決方案處理了約束並有效地解決了問題。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub

以上是具有最大位與的最長子數組的詳細內容。更多資訊請關注PHP中文網其他相關文章！