最长优雅子数组
难度:
标签:
题目描述
代码结果
运行时间: 97 ms, 内存: 29.1 MB
/*
题目思路:
使用Java Stream的方式实现这一题,我们需要找到所有子数组并判断它们是否是优雅的。我们可以利用流和集合的特性来减少重复计算。对于每个起始索引,我们找到所有满足优雅条件的子数组。
*/
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;
public class ElegantSubarrayStream {
public int longestElegantSubarray(int[] nums) {
return IntStream.range(0, nums.length)
.map(i -> {
Set<Integer> seen = new HashSet<>();
int orValue = 0;
for (int j = i; j < nums.length; j++) {
if (seen.stream().anyMatch(x -> (x & nums[j]) != 0)) {
break;
}
seen.add(nums[j]);
orValue |= nums[j];
}
return seen.size();
})
.max()
.orElse(1);
}
}
解释
方法:
这道题解使用了滑动窗口的方法。我们维护一个窗口(由 left 和 right 指针表示),在窗口内所有元素两两进行 AND 操作的结果都必须为 0。通过一个整数 mask 来记录窗口中所有数字的按位或(OR)结果。对于新加入窗口的数字 n,如果 mask 与 n 的 AND 操作结果不为 0,表明 n 与窗口中至少一个数字按位与的结果不为 0,因此需要调整左边界 left 直到 mask 与 n 的 AND 操作结果为 0。窗口扩展和收缩都是线性的,通过这种方式,我们可以高效地找到最长的优雅子数组。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在循环中,如何有效地更新变量`mask`以保证它总是正确地表示窗口内所有数字的按位或结果?
▷🦆
为什么在检测到`mask & n`不为0时,只移动左边界`left`而不考虑右边界`right`的移动?
▷🦆
在移除窗口左边元素的操作中,`mask -= nums[left]`是否正确?按位或操作的逆操作应该是什么?
▷🦆
题解中提到每次新元素加入可能需要调整`left`指针,但是具体如何确定移动`left`的次数和条件以确保`mask & n`为0?
▷