leetcode
leetcode 2101 ~ 2150
按位或最大的最小子数组长度

按位或最大的最小子数组长度

难度:

标签:

题目描述

代码结果

运行时间: 174 ms, 内存: 27.6 MB


/*
 * 思路:
 * 使用Java Stream API可以使代码更简洁。依然需要从后向前遍历数组,并维护最大按位或结果和最小子数组长度。
 */

import java.util.stream.IntStream;

public int[] shortestSubarrayWithMaxBitwiseOrStream(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];
    int maxOr = 0;
    
    IntStream.range(0, n).forEach(i -> {
        int currentOr = 0;
        maxOr |= nums[n - 1 - i];
        int j = n - 1 - i;
        while (j >= 0 && currentOr != maxOr) {
            currentOr |= nums[j];
            j--;
        }
        answer[n - 1 - i] = n - 1 - i - j;
    });
    return answer;
}

解释

方法:

该题解使用了从左向右遍历数组的方式,并且使用了单次遍历的贪心算法来处理每个元素。对于每个元素i,初始化ans[i]=1,意味着最短子数组至少包含自身。然后逆向遍历之前的元素,更新它们的按位或结果和最小子数组长度。如果前面的元素j通过与当前元素i的按位或不再改变(即nums[j] | x == nums[j]),则停止更新,因为进一步的按位或不会得到更大的值。如果发生改变,则更新nums[j]并且重新计算最短长度。这样做是基于这样的假设:如果一个元素需要扩展它的子数组边界来包含之后的元素,那么一定是因为新加入的元素提供了一个新的比特位,使得按位或的结果增大。

时间复杂度:

O(n^2)

空间复杂度:

O(n)

代码细节讲解

🦆
在这个算法中,当内层循环遇到 `nums[j] | x == nums[j]` 时就停止更新,这种停止的条件是否总是正确?是否存在某些情况下需要继续扩展子数组以确保获取到最大的按位或结果?
这种停止更新的条件是基于按位或操作的性质。当发现 `nums[j] | x == nums[j]` 时,意味着x中不存在任何新的比特位能够使nums[j]的按位或结果得到改变。因此,在这种情况下,继续加入后续的元素也不会影响当前的按位或结果,所以可以安全地停止更新。不存在需要继续扩展子数组以确保获取到更大按位或结果的情况,因为所有后续元素的包含都不会改变当前的按位或值。
🦆
算法中提到的最短子数组长度更新为 `i - j + 1`,这是否意味着每次都必须重新计算从当前索引 `i` 到 `j` 的所有可能子数组的按位或结果?这种方法的效率如何?
算法中更新最短子数组长度为 `i - j + 1` 是指在当前元素i和检查到的元素j之间的最短距离。这并不意味着每次都重新计算从i到j所有子数组的按位或结果,而是通过连续更新前面元素的按位或结果来避免重复计算。具体来说,每个元素j在被i影响时就地更新其按位或结果。这种方法提高了效率,因为它避免了对每个子数组进行独立的按位或操作,而是利用了前一个元素的按位或结果作为基础进行增量更新。
🦆
题解中提到使用了贪心算法的思想,这种贪心策略是如何确保每次都能找到最小长度的子数组同时保证按位或值最大?
贪心策略在这个问题中的应用是每次尽可能地缩小子数组的长度,直到找到一个最小的范围,使得子数组内元素的按位或值达到当前能达到的最大值。通过从当前元素向前检查,并在不再增加新的比特位时停止,这个方法确保了在达到最大按位或结果的同时,子数组长度保持最短。这种策略是有效的,因为它总是试图在最早的时刻停止扩展子数组长度,从而确保长度尽可能小,同时通过不断更新按位或结果,保证了按位或值是最大的。
🦆
在题解的实现中,是否考虑了所有数字为0的情况,这种情况下按位或的结果如何影响算法的执行?
在所有数字为0的特殊情况下,按位或的结果始终为0。算法在这种情况下依然可以正确执行,因为每个元素与0的按位或结果还是0,内层循环会在第一次检查时就终止(因为0 | 0 = 0),从而将每个元素的子数组长度设为1。这种情况下算法效率很高,因为每个元素都不需要进行多余的按位或计算,直接确定其子数组长度为1。

相关问题