题目链接：3171.找到按位或最接近 K 的子数组

LogTrick

LogTrick 入门教程

步骤

  • 考虑记录计算结果，$nums[j]$ 保存 $nums[j]$ 到 $nums[i]$ 的 $or$ 值
  • 在记录过程中，当 $x = nums[i]$ 的二进制数对应的集合 $A_i$ 是 $nums[j]$ 对应的集合 $A_j$ 的子集时，即 $(nums[j]\space | \space x) = nums[j]$，一定也是后续集合的子集，继续更新没有意义了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int ans = INT_MAX;
        for (int i = 0; i < nums.size(); i++) {
            int x = nums[i];
            ans = min(ans, abs(x - k));
            for (int j = i - 1; j >= 0 && (x | nums[j]) != nums[j]; j--) {
                nums[j] |= x;
                ans = min(ans, abs(nums[j] - k));
            }
        }
        return ans;
    }
};

滑动窗口

  • 传统的滑动窗口需要考虑维护的运算具有逆运算
  • 右端点的运算值更新可以用一个变量维护，当左端点 left 离开窗口时，需要知道 $nums[left+1]$ … $nums[right]$ 的运算值，
  • 可以在传统滑窗的基础上通过 记录计算结果 的方式，用栈结构维护
  • 当栈空时，重构栈空间（更新栈底），维护右端点的变量清空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int ans = INT_MAX, left = 0, bottom = 0, right_or = 0;
        for (int right = 0; right < nums.size(); right++) {
            right_or |= nums[right];
            while (left <= right && (nums[left] | right_or) > k) {
                ans = min(ans, (nums[left] | right_or) - k);
                left++;
                if (bottom < left) {
                    for (int i = right - 1; i >= left; i--) {
                        nums[i] |= nums[i + 1];
                    }
                    bottom = right;
                    right_or = 0;
                }
            }
            if (left <= right) {
                ans = min(ans, k - (nums[left] | right_or));
            }
        }
        return ans;
    }
};

双栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int n = nums.size();

        vector<int> ls, rs;
        int l = 0, r = 0;
        auto Push = [&]() {
            if (rs.empty()) {
                rs.push_back(nums[r]);
            } else {
                rs.push_back(rs.back() | nums[r]);
            }
            r++;
        };
        auto Pop = [&]() {
            l++;
            if (!ls.empty()) {
                ls.pop_back();
                return;
            }
            rs.clear();
            if (l < r) {
                ls.resize(r - l);
                ls[0] = nums[r - 1];
                for (int i = 1; i < r - l; i++) {
                    ls[i] = ls[i - 1] | nums[r - i - 1];
                }
            }
        };
        auto Get = [&]() {
            return (ls.empty() ? 0 : ls.back()) | (rs.empty() ? 0 : rs.back());
        };

        int res = INT_MAX;
        while (r < n) {
            Push();
            res = min(res, abs(k - Get()));
            while (r - l > 1 && Get() > k) {
                Pop();
                res = min(res, abs(k - Get()));
            }
        }
        return res;
    }
};