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

2025.07.29

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

给你一个长度为 n 下标从 0 开始的数组 nums ，数组中所有数字均为非负整数。对于 0 到 n - 1 之间的每一个下标 i ，你需要找出 nums 中一个 最小 非空子数组，它的起始位置为 i （包含这个位置），同时有 最大 的 按位或运算值。

• 换言之，令 Bij 表示子数组 nums[i...j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 max(Bik) ，其中 i <= k <= n - 1 。

一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。

请你返回一个大小为 n 的整数数组 answer，其中 answer[i]是开始位置为 i ，按位或运算结果最大，且 最短 子数组的长度。

子数组 是数组里一段连续非空元素组成的序列。

暴力大超时

class Solution {
public:vector<int> smallestSubarrays(vector<int>& nums) {int n = nums.size();vector<int> ans(n);for (int i = 0; i < n; i++) {int max = 0;       // 记录从 i 开始的最大按位或结果int min_len = INT_MAX; // 记录最大按位或对应的最短长度int current = 0;   // 当前的按位或结果for (int j = i; j < n; j++) {current |= nums[j];  if (current > max) {max = current;min_len = j - i + 1; }else if (current == max) {min_len = min(min_len, j - i + 1);}} ans[i] = min_len;}return ans;}
};

新学的

将二进制数看做集合，按位或运算看成两个集合的并集。

这里

• 若 nums[j] | a == nums[j]，说明 a 的所有二进制位中为 1 的位置，nums[j] 中已经都是 1（a 没有给 nums[j] 新增任何 1 位）。
• 反之，若 nums[j] | a != nums[j]，说明 a 包含 nums[j] 没有的 1 位，按位或后 nums[j] 会 “增强”（二进制 1 位增多）。

• 当nums[j] | a == nums[j]时，说明当前元素无法被增强，则左侧所有元素都必然无法被增强，所以结束循环

class Solution {
public:vector<int> smallestSubarrays(vector<int>& nums) {int n = nums.size();vector<int> ans(n);for (int i = 0; i < nums.size(); i++) {int a = nums[i];ans[i] = 1;for (int j = i - 1; j >= 0 && (nums[j] | a) != nums[j]; j--) {nums[j] = nums[j] | a;ans[j] = i - j + 1;}}return ans;}
};