按位与最大的最长子数组
难度:
标签:
题目描述
代码结果
运行时间: 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的子数组会产生最大的按位与结果?
▷🦆
如果数组中存在多段相同的最长连续maxVal子数组,该算法是否能正确地返回其中一段的长度?
▷🦆
算法中使用了两次遍历数组,第一次是找最大值,第二次是找最长连续子数组。这种方法是否最高效,还有没有其他可能的优化方法?
▷🦆
算法在遍历寻找连续maxVal子数组时,如何处理数组末尾是maxVal的情况?是否有可能出现索引越界?
▷