子数组之「与」「或」

6189. 按位与最大的最长子数组

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

本篇文章总结一下子数组和「与」「或」相结合的两个题目

按位与最大的最长子数组

题目详情可见 按位与最大的最长子数组

比赛的时候浪费了很多时间，没有一眼看出题目中隐藏的细节

这里就需要清楚「与」运算的一个特点：x & x = x；x ^ y = y，其中y < x

简单来说，相同的两个数相与，还是等于原数；不同的两个数相与，结果的是较小的那个数

对于一个数组[a, b, c, d]，以a开头的所有子数组有：[a], [a, b], [a, b, c], [a, b, c, d]

那么一定存在：(a) >= (a & b) >= (a & b & c) >= (a & b & c & d)

所以，「与运算」具有单调非递增的特性

既然需要得到「按位与」最大的最长子数组，等价于找最大值连续的最大长度

例：1234452444332，这个例子中最大最长子数组为444

下面给出代码：

xxxxxxxxxx
public int longestSubarray(int[] nums) {
    // 求出最大值
    int max = Arrays.stream(nums).max().getAsInt();
    int ans = 0, cnt = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != max) cnt = 0;
        else cnt++;
        ans = Math.max(ans, cnt);
    }
    return ans;
}

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

题目详情可见 按位或最大的最小子数组长度

和「与运算」相同，「或运算」也有一个特点：x | x = x；x | y = y，其中y > x

简单来说，相同的两个数相或，还是等于原数；不同的两个数相或，结果的是较大的那个数

同样的，举一个例子，但是为了和本题相互呼应，把例子稍微改改

对于一个数组[a, b, c, d]，以d结尾的所有子数组有：[a, b, c, d], [b, c, d], [c, d], [d]

那么一定存在：(a | b | c | d) >= (b | c | d) >= (c | d) >= (d)

所以，「或运算」具有单调非递减的特性

先给出代码，结合注释食用更佳：

public int[] smallestSubarrays(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    // 从左向右遍历 👉
    for (int i = 0; i < n; i++) {
        int x = nums[i];
        ans[i] = 1;
        // 从 i - 1 向左遍历 👈
        for (int j = i - 1; j >= 0; j--) {
            // 相等表示 x = nums[j]，为了最短，选择不相或
            // 而且 j - 1 及前面的都不用再判断了，因为 nums[j - 1] >= nums[j]，所以不需要判断
            if ((nums[j] | x) == nums[j]) break;
            // 注意：nums[j] 会累计或运算
            nums[j] |= x;
            // 更新结果
            ans[j] = i - j + 1;
        }
    }
    return ans;
}