本文涉及的基础知识点

C++二分查找
拆位法（分治法）

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

给你一个长度为 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 ，按位或运算结果最大，且 最短 子数组的长度。
子数组 是数组里一段连续非空元素组成的序列。
示例 1：
输入：nums = [1,0,2,1,3]
输出：[3,3,2,2,1]
解释：
任何位置开始，最大按位或运算的结果都是 3 。

• 下标 0 处，能得到结果 3 的最短子数组是 [1,0,2] 。
• 下标 1 处，能得到结果 3 的最短子数组是 [0,2,1] 。
• 下标 2 处，能得到结果 3 的最短子数组是 [2,1] 。
• 下标 3 处，能得到结果 3 的最短子数组是 [1,3] 。
• 下标 4 处，能得到结果 3 的最短子数组是 [3] 。
  所以我们返回 [3,3,2,2,1] 。
  示例 2：
  输入：nums = [1,2]
  输出：[2,1]
  解释：
  下标 0 处，能得到最大按位或运算值的最短子数组长度为 2 。
  下标 1 处，能得到最大按位或运算值的最短子数组长度为 1 。
  所以我们返回 [2,1] 。

分治+二分查找

nums[i…j] 第m位存在1，则max(Bik) 的此位一定是1。由于要求最短子数组。令k1是nums[i…]m位为1的最小下标。则k <=k1。
indexs[m]记录第m位为1的nums元素下标。
分别对各位求k1，结果就是k1的最大值。注意：k1如果不存在则忽略。

代码

核心代码

class Solution {
		public:
			vector<int> smallestSubarrays(vector<int>& nums) {
				const int N = 30;
				vector<int> indexs[N];
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < nums.size(); j++) {
						if ((1 << i) & nums[j]) {
							indexs[i].emplace_back(j);
						}
					}
				}
				vector<int> ret;
				for (int i = 0; i < nums.size(); i++) {
					int end = i;
					for (int j = 0; j < N; j++) {
						auto it = lower_bound(indexs[j].begin(), indexs[j].end(), i);
						if (indexs[j].end() == it) { continue; }	
						end = max(end, *it);
					}
					ret.emplace_back(end-i+1);
				}
				return ret;
			}
		};

单元测试

vector<int> nums;
		TEST_METHOD(TestMethod1)
		{
			nums = { 1 };
			auto res = Solution().smallestSubarrays(nums);
			AssertEx({ 1 }, res);
		}
		TEST_METHOD(TestMethod11)
		{
			nums = { 1,0,2,1,3 };
			auto res = Solution().smallestSubarrays(nums);
			AssertEx({ 3,3,2,2,1 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 1,2 };
			auto res = Solution().smallestSubarrays(nums);
			AssertEx({ 2,1 }, res);
		}