smallest-subarrays-with-maximum-bitwise-or

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 0-indexed array <code>nums</code> of length <code>n</code>, consisting of non-negative integers. For each index <code>i</code> from <code>0</code> to <code>n - 1</code>, you must determine the size of the minimum sized non-empty subarray of <code>nums</code> starting at <code>i</code> (inclusive) that has the maximum possible bitwise OR.

<ul>
	<li>In other words, let <code>Bij</code> be the bitwise OR of the subarray <code>nums[i...j]</code>. You need to find the smallest subarray starting at <code>i</code>, such that bitwise OR of this subarray is equal to <code>max(Bik)</code> where <code>i &lt;= k &lt;= n - 1</code>.</li>
</ul>

The bitwise OR of an array is the bitwise OR of all the numbers in it.

Return an integer array <code>answer</code> of size <code>n</code> where <code>answer[i]</code> is the length of the minimum sized subarray starting at <code>i</code> with maximum bitwise OR.

A subarray is a contiguous non-empty sequence of elements within an array.

&nbsp;
Example 1:

<pre>
Input: nums = [1,0,2,1,3]
Output: [3,3,2,2,1]
Explanation:
The maximum possible bitwise OR starting at any index is 3. 
- Starting at index 0, the shortest subarray that yields it is [1,0,2].
- Starting at index 1, the shortest subarray that yields the maximum bitwise OR is [0,2,1].
- Starting at index 2, the shortest subarray that yields the maximum bitwise OR is [2,1].
- Starting at index 3, the shortest subarray that yields the maximum bitwise OR is [1,3].
- Starting at index 4, the shortest subarray that yields the maximum bitwise OR is [3].
Therefore, we return [3,3,2,2,1]. 
</pre>

Example 2:

<pre>
Input: nums = [1,2]
Output: [2,1]
Explanation:
Starting at index 0, the shortest subarray that yields the maximum bitwise OR is of length 2.
Starting at index 1, the shortest subarray that yields the maximum bitwise OR is of length 1.
Therefore, we return [2,1].
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 109</code></li>
</ul>

smallestSubarrays

Smallest Subarrays With Maximum Bitwise OR

Merge k Sorted Lists

merge-k-sorted-lists

合并 K 个升序链表

Bitwise ORs of Subarrays

bitwise-ors-of-subarrays

子数组按位或操作

Longest Subarray With Maximum Bitwise AND

longest-subarray-with-maximum-bitwise-and

按位与最大的最长子数组

Bit Manipulation

Array

Binary Search

Sliding Window

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

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

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

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

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

&nbsp;

示例 1：

<pre>输入：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] 。
</pre>

示例 2：

<pre>输入：nums = [1,2]
输出：[2,1]
解释：
下标 0 处，能得到最大按位或运算值的最短子数组长度为 2 。
下标 1 处，能得到最大按位或运算值的最短子数组长度为 1 。
所以我们返回 [2,1] 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 109</code></li>
</ul>