shelterofly

目标

给你一个长度为 n 的整数数组 nums 。

考虑 nums 中进行 按位与（bitwise AND）运算得到的值 最大 的 非空 子数组。

• 换句话说，令 k 是 nums 任意 子数组执行按位与运算所能得到的最大值。那么，只需要考虑那些执行一次按位与运算后等于 k 的子数组。

返回满足要求的 最长 子数组的长度。

数组的按位与就是对数组中的所有数字进行按位与运算。

子数组 是数组中的一个连续元素序列。

示例 1：

输入：nums = [1,2,3,3,2,2]
输出：2
解释：
子数组按位与运算的最大值是 3 。
能得到此结果的最长子数组是 [3,3]，所以返回 2 。

示例 2：

输入：nums = [1,2,3,4]
输出：1
解释：
子数组按位与运算的最大值是 4 。
能得到此结果的最长子数组是 [4]，所以返回 1 。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

思路

两个数按位与的结果一定不会比这两个数更大。问题转化为连续的最大值长度。

代码

/**
 * @date 2025-07-30 10:28
 */
public class LongestSubarray2419 {

    public int longestSubarray(int[] nums) {
        int n = nums.length;
        int max = Arrays.stream(nums).max().getAsInt();
        int res = 1;
        int i = 0;
        while (i < n){
            int l = 0;
            while (i < n && nums[i++] == max){
                l++;
            }
            res = Math.max(res, l);
        }
        return res;
    }
}

性能

目标

给你一个长度为 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] 。

说明：

• n == nums.length
• 1 <= n <= 10^5
• 0 <= nums[i] <= 10^9

思路

有一个数组 nums，求以每个元素为起点的子数组，取得最大或值的最小长度。res[i] 表示以 i 为起点的子数组中，数组元素按位或取得最大值时的最小长度。

枚举右端点，将当前元素与前面的元素进行或运算，并覆盖原来的元素值。对于当前元素 j，nums[i] 中存的是 i ~ j 的或值，站在集合的角度来看，nums[i + 1] 是 nums[i] 的子集。在进行或运算时，如果或值没有变大，就没有必要继续向前了。

代码

/**
 * @date 2025-07-29 9:39
 */
public class SmallestSubarrays2411 {

    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            res[i] = 1;
            for (int j = i - 1; j >= 0 && (num | nums[j]) != nums[j]; j--) {
                nums[j] |= num;
                res[j] = i - j + 1;
            }
        }
        return res;
    }

}

性能

目标

给你一个字符串 s 和两个整数 x 和 y 。你可以执行下面两种操作任意次。

• 删除子字符串 "ab" 并得到 x 分。
  • 比方说，从 "cabxbae" 删除 ab ，得到 "cxbae" 。
• 删除子字符串"ba" 并得到 y 分。
  • 比方说，从 "cabxbae" 删除 ba ，得到 "cabxe" 。

请返回对 s 字符串执行上面操作若干次能得到的最大得分。

示例 1：

输入：s = "cdbcbbaaabab", x = 4, y = 5
输出：19
解释：
- 删除 "cdbcbbaaabab" 中加粗的 "ba" ，得到 s = "cdbcbbaaab" ，加 5 分。
- 删除 "cdbcbbaaab" 中加粗的 "ab" ，得到 s = "cdbcbbaa" ，加 4 分。
- 删除 "cdbcbbaa" 中加粗的 "ba" ，得到 s = "cdbcba" ，加 5 分。
- 删除 "cdbcba" 中加粗的 "ba" ，得到 s = "cdbc" ，加 5 分。
总得分为 5 + 4 + 5 + 5 = 19 。

示例 2：

输入：s = "aabbaaxybbaabb", x = 5, y = 4
输出：20

说明：

• 1 <= s.length <= 10^5
• 1 <= x, y <= 10^4
• s 只包含小写英文字母。

思路

贪心策略，优先处理分值高的字符串。

代码

/**
 * @date 2025-07-23 9:01
 */
public class MaximumGain1717 {

    public int maximumGain(String s, int x, int y) {
        char prev, cur;
        int max, min;
        if (x > y) {
            prev = 'a';
            cur = 'b';
            max = x;
            min = y;
        } else {
            prev = 'b';
            cur = 'a';
            max = y;
            min = x;
        }
        Deque<Character> q = new ArrayDeque<>();
        q.push('^');
        int n = s.length();
        int res = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (q.peek() == prev && c == cur) {
                q.pop();
                res += max;
            } else {
                q.push(c);
            }
        }
        q.removeLast();
        Deque<Character> p = new ArrayDeque<>();
        p.push('^');
        while (!q.isEmpty()) {
            if (q.peekLast() == prev && p.peek() == cur) {
                q.removeLast();
                p.pop();
                res += min;
            } else {
                p.push(q.removeLast());
            }
        }
        return res;
    }

}

性能