[LeetCode] 每日一题 2680. 最大或值（前缀和的位运算版本）

题目链接

https://leetcode.cn/problems/maximum-or

题目描述

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k 。每一次操作中，你可以选择一个数并将它乘 2 。

你最多可以进行 k 次操作，请你返回 nums[0] | nums[1] | ... | nums[n - 1] 的最大值。

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

示例输入

示例 1

输入：nums = [12,9], k = 1
输出：30
解释：如果我们对下标为 1 的元素进行操作，新的数组为 [12,18] 。此时得到最优答案为 12 和 18 的按位或运算的结果，也就是 30 。

示例 2

输入：nums = [8,1,2], k = 2
输出：35
解释：如果我们对下标 0 处的元素进行操作，得到新数组 [32,1,2] 。此时得到最优答案为 32|1|2 = 35 。

提示

• 1 <= nums.length <= 105

• 1 <= nums[i] <= 109

• 1 <= k <= 15

解题思路

这道题的核心是利用 按位或（|） 的运算性质，并结合 前缀与后缀的技巧 进行优化。由于按位或运算是单调的，每次将某个数乘 2 后，只有该数的二进制位会改变，因此与其他数的按位或结果也会随之变化

如果我们随意选择多个数分别进行乘 2 操作，最终的或值往往不如 选定一个数，让它连续乘 k 次 2 产生的效果更优。因此，我们的策略是遍历数组，尝试让某个元素左移 k 位，然后再与数组剩余元素的按位或值进行比较，找出最大值

为了避免重复遍历数组，我们可以使用 前缀或 和 后缀或 预处理出数组中所有元素的或值。这样，每次计算某个元素变换后的最大或值时，我们可以直接利用前缀和后缀的结果，而不用重新遍历整个数组，大大降低了时间复杂度

代码实现

class Solution {
    public long maximumOr(int[] nums, int k) {
        long[] suf = new long[nums.length + 1];
        for (int i = nums.length - 1; i >= 0; i--) {
            suf[i] = suf[i + 1] | nums[i];
        }
        long ans = 0, pre = 0;
        for (int i = 0; i < nums.length; i++) {
            ans = Math.max(ans, pre | (long)nums[i] << k | suf[i + 1]);
            pre |= nums[i];
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)。前缀或和后缀或各需 O(n) 预处理，之后遍历数组进行 O(n) 次计算，因此总复杂度为 O(n)

• 空间复杂度：O(n)。额外使用了后缀或数组 suf，空间占用为 O(n)

总结

这道题巧妙地运用了按位或的性质，并结合前缀或和后缀或优化计算，使得每次尝试将某个数左移 k 位时，能够高效计算最终的或值，避免了暴力解法的 O(n^2) 复杂度。通过这样的优化，我们可以在 O(n) 时间内找到最大可能的或值，适用于大规模数据的情况

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。