題目連結:
題目意譯:
你被給定一個索引值從 0 開始且長度為 n 的陣列 nums,其由非負整數所組成。對於每個索引值 i 從 0 到 n - 1,你必須判斷出 nums 中從 i 開始(含)的最小非空子陣列之大小,使得該子陣列有著最大的按位元 OR(Bitwise OR)之值。
換句話說,令 Bij 為子陣列 nums[i...j] 的按位元 OR 之值。你需要找到從 i 開始的最小子陣列,使得其按位元 OR 之值等於 max(Bik),其中 i ≦ k ≦ n - 1。
一陣列按位元 OR 之值為當中所有數字按位元 OR 之後的結果。
回傳一個長度為 n 的整數陣列 answer,其中 answer[i] 為從 i 開始的、有著最大按位元 OR 之值的最小子陣列之長度。
一個子陣列為一陣列中的一個非空連續元素序列。
限制:
n == nums.length
1 ≦ n ≦ 10 ^ 5
0 ≦ nums[i] ≦ 10 ^ 9
範例測資:
範例 1:
輸入: nums = [1,0,2,1,3]
輸出: [3,3,2,2,1]
解釋:
從任一索引值開始的最大按位元 OR 之值為 3。
- 從索引值 0 開始,可以得到該值的最短子陣列為 [1,0,2]。
- 從索引值 1 開始,可以得到該值的最短子陣列為 [0,2,1]。
- 從索引值 2 開始,可以得到該值的最短子陣列為 [2,1]。
- 從索引值 3 開始,可以得到該值的最短子陣列為 [1,3]。
- 從索引值 4 開始,可以得到該值的最短子陣列為 [3]。
因此,我們回傳 [3,3,2,2,1]。
範例 2:
輸入: nums = [1,2]
輸出: [2,1]
解釋:
- 從索引值 0 開始,可以得到最大按位元 OR 之值的最短子陣列之長度為 2。
- 從索引值 1 開始,可以得到最大按位元 OR 之值的最短子陣列之長度為 1。
因此,我們回傳 [2,1]。
解題思維:
其實跟
這題基本一樣(都可以用滑動視窗(Sliding Window)解),而且該題剛好也有用到按位元 OR 之值,不過是往左延伸。所以想要套用類似的作法需要反著掃過 nums。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。