leetcode
leetcode 2101 ~ 2150
按位与最大的最长子数组

按位与最大的最长子数组

难度:

标签:

题目描述

代码结果

运行时间: 55 ms, 内存: 28.4 MB


/*
 * 思路:
 * 1. 先找到数组中的最大值maxVal。
 * 2. 使用Java Stream API来过滤和计算最长的子数组长度。
 */

import java.util.Arrays;

public class Solution {
    public int longestSubarray(int[] nums) {
        int maxVal = Arrays.stream(nums).max().getAsInt();
        int[] lengths = Arrays.stream(nums)
                .map(num -> num == maxVal ? 1 : 0)
                .toArray();

        int maxLength = 0;
        int currentLength = 0;
        for (int length : lengths) {
            if (length == 1) {
                currentLength++;
                maxLength = Math.max(maxLength, currentLength);
            } else {
                currentLength = 0;
            }
        }
        return maxLength;
    }
}

解释

方法:

此题解的思路首先是找到数组中的最大值maxVal,因为只有包含最大值的子数组才可能得到最大的按位与结果。接着,遍历数组,寻找包含最大值maxVal的最长连续子数组。通过设置一个计数器cnt来记录最长的连续子数组的长度。当遇到与maxVal相等的元素时,开始计数,直到遇到不等的元素为止,每次都更新最大的连续长度cnt。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在确定最大值maxVal之后,为什么可以断定包含maxVal的子数组会产生最大的按位与结果?
按位与操作会对二进制的每一位进行与运算,即只有所有位都是1时结果才为1。因此,包含较大数字的子数组在进行按位与操作时,更有可能保持较高的位为1,从而得到更大的结果。特别是最大值本身,其二进制中的高位1在与操作中不会因为其他更小的数而被置0(因为这些数的相应位不能比最大值更高)。因此,包含数组中的最大值的子数组在进行按位与操作时,更可能得到最大的结果。
🦆
如果数组中存在多段相同的最长连续maxVal子数组,该算法是否能正确地返回其中一段的长度?
是的,该算法能正确返回其中一段的长度。算法通过遍历整个数组来确定所有包含maxVal的连续子数组,并利用一个计数器记录下这些子数组中的最大长度。无论maxVal出现在数组中的哪个位置,只要是最长的连续子数组,它们的长度都会被正确记录和返回。
🦆
算法中使用了两次遍历数组,第一次是找最大值,第二次是找最长连续子数组。这种方法是否最高效,还有没有其他可能的优化方法?
这种方法相对简单易懂,但确实存在一定的优化空间。例如,可以通过一次遍历同时完成最大值的查找和最长连续子数组的确定。在这一次遍历中,同时更新最大值和检查当前值是否为最大值,如果是,则继续计算连续子数组的长度;如果不是,则重置长度计数。这样可以减少一次完整的数组遍历,提高算法效率。
🦆
算法在遍历寻找连续maxVal子数组时,如何处理数组末尾是maxVal的情况?是否有可能出现索引越界?
算法在遍历时,会检查每个元素是否等于maxVal,并在找到maxVal时进入内部循环继续向后查找,直到遇到非maxVal元素或达到数组末尾。内部循环的条件包括i < n,保证i不会超出数组的界限,因此不会出现索引越界。当数组末尾是maxVal时,内部循环会正常结束并更新最长长度,然后外部循环由于i等于n也将结束,整个过程安全且正确。

相关问题