Hard

题目描述

给你一个整数数组 nums。

如果一个子数组中所有元素的按位或运算结果等于该子数组中至少一个元素，则该子数组被称为好子数组。

返回 nums 中好子数组的数量。

这里，两个整数 a 和 b 的按位或运算用 a | b 表示。

示例 1：

输入：nums = [4,2,3]

输出：4

解释：

nums 的子数组有：

子数组按位或是否存在于子数组中
[4]4 = 4是
[2]2 = 2是
[3]3 = 3是
[4, 2]4 | 2 = 6否
[2, 3]2 | 3 = 3是
[4, 2, 3]4 | 2 | 3 = 7否

因此，nums 的好子数组是 [4]、[2]、[3] 和 [2, 3]。所以答案是 4。

示例 2：

输入：nums = [1,3,1]

输出：6

解释：

包含 3 的任何子数组的按位或都等于 3，而只包含 1 的子数组的按位或等于 1。

在这两种情况下，结果都存在于子数组中，所以所有子数组都是好的，答案是 6。

约束：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9

解题思路

根据题意，一个好子数组的按位或结果必须等于其中某个元素。关键观察是：一个子数组是好的当且仅当其按位或等于其最大元素。

这是因为按位或运算具有单调性（只会增加比特位，不会减少），所以子数组的按位或必定大于等于最大元素。当按位或等于最大元素时，说明最大元素包含了子数组中所有元素的所有比特位。

解法思路：

  1. 单调栈找范围：使用单调递减栈为每个位置 i 找到以 nums[i] 为最大值的左右边界 [L[i], R[i]]

  2. 比特位约束：预处理每个比特位在数组中的出现位置。对于位置 i，需要缩小范围 [L[i], R[i]]，排除那些包含 nums[i] 中未设置比特位的位置

  3. 计算贡献：对于每个位置 i，其有效范围内的子数组数量为 (i - effective_left + 1) * (effective_right - i + 1)

这种方法的核心是利用按位或的单调性和最大元素的特性，将问题转化为区间计数问题。

时间复杂度为 O(n log max(nums))，其中 log max(nums) 来自于处理比特位（最多32位）。

代码实现

class Solution {
public:
    long long countGoodSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n), right(n);
        
        // 使用单调栈找到每个位置作为最大值的范围
        stack<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && nums[st.top()] <= nums[i]) {
                st.pop();
            }
            left[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }
        
        while (!st.empty()) st.pop();
        
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && nums[st.top()] < nums[i]) {
                st.pop();
            }
            right[i] = st.empty() ? n : st.top();
            st.push(i);
        }
        
        // 预处理每个比特位的前一个和后一个位置
        vector<vector<int>> prevBit(32), nextBit(32);
        for (int bit = 0; bit < 32; bit++) {
            prevBit[bit].resize(n);
            nextBit[bit].resize(n);
            
            int lastPos = -1;
            for (int i = 0; i < n; i++) {
                prevBit[bit][i] = lastPos;
                if (nums[i] & (1 << bit)) {
                    lastPos = i;
                }
            }
            
            lastPos = n;
            for (int i = n - 1; i >= 0; i--) {
                nextBit[bit][i] = lastPos;
                if (nums[i] & (1 << bit)) {
                    lastPos = i;
                }
            }
        }
        
        long long result = 0;
        
        for (int i = 0; i < n; i++) {
            int effectiveLeft = left[i] + 1;
            int effectiveRight = right[i] - 1;
            
            // 对于nums[i]中未设置的每个比特位，缩小有效范围
            for (int bit = 0; bit < 32; bit++) {
                if (!(nums[i] & (1 << bit))) {
                    effectiveLeft = max(effectiveLeft, prevBit[bit][i] + 1);
                    effectiveRight = min(effectiveRight, nextBit[bit][i] - 1);
                }
            }
            
            if (effectiveLeft <= i && i <= effectiveRight) {
                long long leftCount = i - effectiveLeft + 1;
                long long rightCount = effectiveRight - i + 1;
                result += leftCount * rightCount;
            }
        }
        
        return result;
    }
};

class Solution:
    def countGoodSubarrays(self, nums: list[int]) -> int:
        n = len(nums)
        left = [0] * n
        right = [0] * n
        
        # 使用单调栈找到每个位置作为最大值的范围
        stack = []
        for i in range(n):
            while stack and nums[stack[-1]] <= nums[i]:
                stack.pop()
            left[i] = stack[-1] if stack else -1
            stack.append(i)
        
        stack.clear()
        
        for i in range(n-1, -1, -1):
            while stack and nums[stack[-1]] < nums[i]:
                stack.pop()
            right[i] = stack[-1] if stack else n
            stack.append(i)
        
        # 预处理每个比特位的前一个和后一个位置
        prev_bit = [[0] * n for _ in range(32)]
        next_bit = [[0] * n for _ in range(32)]
        
        for bit in range(32):
            last_pos = -1
            for i in range(n):
                prev_bit[bit][i] = last_pos
                if nums[i] & (1 << bit):
                    last_pos = i
            
            last_pos = n
            for i in range(n-1, -1, -1):
                next_bit[bit][i] = last_pos
                if nums[i] & (1 << bit):
                    last_pos = i
        
        result = 0
        
        for i in range(n):
            effective_left = left[i] + 1
            effective_right = right[i] - 1
            
            # 对于nums[i]中未设置的每个比特位，缩小有效范围
            for bit in range(32):
                if not (nums[i] & (1 << bit)):
                    effective_left = max(effective_left, prev_bit[bit][i] + 1)
                    effective_right = min(effective_right, next_bit[bit][i] - 1)
            
            if effective_left <= i <= effective_right:
                left_count = i - effective_left + 1
                right_count = effective_right - i + 1
                result += left_count * right_count
        
        return result

public class Solution {
    public long CountGoodSubarrays(int[] nums) {
        int n = nums.Length;
        int[] left = new int[n];
        int[] right = new int[n];
        
        // 使用单调栈找到每个位置作为最大值的范围
        Stack<int> stack = new Stack<int>();
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && nums[stack.Peek()] <= nums[i]) {
                stack.Pop();
            }
            left[i] = stack.Count == 0 ? -1 : stack.Peek();
            stack.Push(i);
        }
        
        stack.Clear();
        
        for (int i = n - 1; i >= 0; i--) {
            while (stack.Count > 0 && nums[stack.Peek()] < nums[i]) {
                stack.Pop();
            }
            right[i] = stack.Count == 0 ? n : stack.Peek();
            stack.Push(i);
        }
        
        // 预处理每个比特位的前一个和后一个位置
        int[,] prevBit = new int[32, n];
        int[,] nextBit = new int[32, n];
        
        for (int bit = 0; bit < 32; bit++) {
            int lastPos = -1;
            for (int i = 0; i < n; i++) {
                prevBit[bit, i] = lastPos;
                if ((nums[i] & (1 << bit)) != 0) {
                    lastPos = i;
                }
            }
            
            lastPos = n;
            for (int i = n - 1; i >= 0; i--) {
                nextBit[bit, i] = lastPos;
                if ((nums[i] & (1 << bit)) != 0) {
                    lastPos = i;
                }
            }
        }
        
        long result = 0;
        
        for (int i = 0; i < n; i++) {
            int effectiveLeft = left[i] + 1;
            int effectiveRight = right[i] - 1;
            
            // 对于nums[i]中未设置的每个比特位，缩小有效范围
            for (int bit = 0; bit < 32; bit++) {
                if ((nums[i] & (1 << bit)) == 0) {
                    effectiveLeft = Math.Max(effectiveLeft, prevBit[bit, i] + 1);
                    effectiveRight = Math.Min(effectiveRight, nextBit[bit, i] - 1);
                }
            }
            
            if (effectiveLeft <= i && i <= effectiveRight) {
                long leftCount = i - effectiveLeft + 1;
                long rightCount = effectiveRight - i + 1;
                result += leftCount * rightCount;
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var countGoodSubarrays = function(nums) {
    let count = 0;
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        let or = 0;
        const seen = new Set();
        
        for (let j = i; j < n; j++) {
            or |= nums[j];
            seen.add(nums[j]);
            
            if (seen.has(or)) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n × log(max(nums)))
空间复杂度O(n × log(max(nums)))

其中 n 为数组长度，log(max(nums)) 约为 32（32位整数的比特位数）。单调栈操作为 O(n)，比特位预处理为 O(32n)，总体时间复杂度为 O(32n) = O(n)。