leetcode
leetcode 2051 ~ 2100
最长优雅子数组

最长优雅子数组

难度:

标签:

题目描述

代码结果

运行时间: 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`以保证它总是正确地表示窗口内所有数字的按位或结果?
在滑动窗口中,每次向右移动`right`指针以包含一个新元素时,我们通过`mask |= nums[right]`来更新`mask`。这个操作确保`mask`包含了当前窗口内所有元素的按位或结果。当需要从窗口中移除左侧元素时,应该正确地更新`mask`以反映当前窗口状态,但这需要单独处理每个位,而不是简单地使用减法。
🦆
为什么在检测到`mask & n`不为0时,只移动左边界`left`而不考虑右边界`right`的移动?
当`mask & n`不为0时,这意味着新考虑的元素`n`与窗口中至少一个元素按位与的结果不为0。移动左边界`left`是为了从窗口中移除元素,直到`mask & n`为0,从而可以安全地将元素`n`加入窗口而不违反条件。右边界`right`代表当前尝试加入到窗口的元素的位置,所以在这种情况下不应该移动`right`,因为我们需要尝试将其纳入窗口中。
🦆
在移除窗口左边元素的操作中,`mask -= nums[left]`是否正确?按位或操作的逆操作应该是什么?
`mask -= nums[left]`操作是不正确的,因为按位或操作的逆操作不是简单的减法。正确的方法是重新计算`mask`,即从当前`left`指针的新位置重新对窗口内的所有元素进行按位或操作。另一种更高效的方式是使用额外的数据结构(如计数数组)来跟踪每个位的出现次数,从而动态更新`mask`。
🦆
题解中提到每次新元素加入可能需要调整`left`指针,但是具体如何确定移动`left`的次数和条件以确保`mask & n`为0?
当检测到`mask & n`不为0时,意味着新加入的元素`n`与窗口中至少一个元素的按位与不为0。此时,需要逐步移动左边界`left`,每次移动都从`mask`中移除最左侧元素的贡献,并检查`mask & n`。这一过程重复进行,直到`mask & n`的结果为0,此时窗口中的所有元素与`n`的按位与均为0,使得`n`可以被加入窗口。具体的移动次数取决于窗口中元素的具体值和它们的按位关系。

相关问题