目标

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

示例 1：

输入：nums = [12,6,1,2,7]
输出：77
解释：下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。
可以证明不存在值大于 77 的有序下标三元组。

示例 2：

输入：nums = [1,10,3,4,19]
输出：133
解释：下标三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。
可以证明不存在值大于 133 的有序下标三元组。 

示例 3：

输入：nums = [1,2,3]
输出：0
解释：唯一的下标三元组 (0, 1, 2) 的值是一个负数，(nums[0] - nums[1]) * nums[2] = -3 。因此，答案是 0 。

说明：

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

思路

求数组 nums 的下标 0 <= i < j < k < n 时 (nums[i] - nums[j]) * nums[k] 的最大值。

与 2873.有序三元组中的最大值I 相比数组最大长度变成了 10^5。

只能选择枚举 k，维护前缀最大值，以及最大值与当前元素的最大差值。

由于题目要求负值取 0 所以更新最大值与最大差值的顺序不影响。但是更新 maxDiff * nums[k] 就必须放在第一位，因为这时 maxDiff 还未更新，还是 k 左侧的最大差值。

代码

/**
 * @date 2025-04-03 0:41
 */
public class MaximumTripletValue2874 {

    public long maximumTripletValue(int[] nums) {
        long res = 0L;
        int n = nums.length;
        int max = 0;
        long maxDiff = 0;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, maxDiff * nums[i]);
            maxDiff = Math.max(maxDiff, max - nums[i]);
            max = Math.max(max, nums[i]);
        }
        return res;
    }

}

性能

目标

给你一个下标从 0 开始、大小为 m x n 的二维矩阵 grid ，请你求解大小同样为 m x n 的答案矩阵 answer 。

矩阵 answer 中每个单元格 (r, c) 的值可以按下述方式进行计算：

• 令 topLeft[r][c] 为矩阵 grid 中单元格 (r, c) 左上角对角线上 不同值 的数量。
• 令 bottomRight[r][c] 为矩阵 grid 中单元格 (r, c) 右下角对角线上 不同值 的数量。

然后 answer[r][c] = |topLeft[r][c] - bottomRight[r][c]| 。

返回矩阵 answer 。

矩阵对角线 是从最顶行或最左列的某个单元格开始，向右下方向走到矩阵末尾的对角线。

如果单元格 (r1, c1) 和单元格 (r, c) 属于同一条对角线且 r1 < r ，则单元格 (r1, c1) 属于单元格 (r, c) 的左上对角线。类似地，可以定义右下对角线。

示例 1：

输入：grid = [[1,2,3],[3,1,5],[3,2,1]]
输出：[[1,1,0],[1,0,1],[0,1,1]]
解释：第 1 个图表示最初的矩阵 grid 。 
第 2 个图表示对单元格 (0,0) 计算，其中蓝色单元格是位于右下对角线的单元格。
第 3 个图表示对单元格 (1,2) 计算，其中红色单元格是位于左上对角线的单元格。
第 4 个图表示对单元格 (1,1) 计算，其中蓝色单元格是位于右下对角线的单元格，红色单元格是位于左上对角线的单元格。
- 单元格 (0,0) 的右下对角线包含 [1,1] ，而左上对角线包含 [] 。对应答案是 |1 - 0| = 1 。
- 单元格 (1,2) 的右下对角线包含 [] ，而左上对角线包含 [2] 。对应答案是 |0 - 1| = 1 。
- 单元格 (1,1) 的右下对角线包含 [1] ，而左上对角线包含 [1] 。对应答案是 |1 - 1| = 0 。
其他单元格的对应答案也可以按照这样的流程进行计算。

示例 2：

输入：grid = [[1]]
输出：[[0]]
解释：- 单元格 (0,0) 的右下对角线包含 [] ，左上对角线包含 [] 。对应答案是 |0 - 0| = 0 。

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m, n, grid[i][j] <= 50

思路

计算矩阵元素左上对角线的不同元素个数与右下对角线的不同元素个数的差的绝对值。即将元素所在的左上右下对角线，以当前元素为分界点（不包括当前元素），分成左上与右下两部分，计算每部分不同元素的个数，取差的绝对值。

暴力解法是枚举每个格子的左上右下元素，每一对角线都要遍历它所包含的元素个数次。

可以直接按对角线遍历，先记录前缀中的不同元素个数，然后再倒着遍历，计算差值的绝对值。

网友提到由于元素值不大，可以将其保存到 long 型数字中。

代码

/**
 * @date 2025-03-25 0:12
 */
public class DifferenceOfDistinctValues2711 {

    public int[][] differenceOfDistinctValues(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] res = new int[m][n];
        for (int i = 0; i < m + n - 1; i++) {
            int row = i / n < 1 ? 0 : i - n + 1 % m;
            int col = row > 0 ? 0 : n - 1 - i;
            Set<Integer> set = new HashSet<>();
            while (row < m && col < n){
                res[row][col] = set.size();
                set.add(grid[row][col]);
                row++;
                col++;
            }
            row--;
            col--;
            set.clear();
            while (row >= 0 && col >= 0){
                res[row][col] = Math.abs(res[row][col] - set.size());
                set.add(grid[row][col]);
                row--;
                col--;
            }
        }
        return res;
    }

}

性能

目标

给你一个下标从 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 <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= 15

思路

有一个整数数组 nums，最多可以对它执行 k 次操作，每次操作可以任选一个数将其左移 1 位。求操作后数组所有元素的最大或值。

操作集中到同一个数上可以将最高有效位移到最高，少一次操作最高位就低一位。问题的关键在于，如果所有数字都有相同的最高有效位，移哪个是不确定的。

这时就需要枚举操作数了，每选择一个操作数就需要重新计算其余元素的或值。由于或运算没有逆运算，我们无法撤销已经或进去的值。

直接的想法是计算或前缀、后缀，枚举所有元素，将其左移 k 次，然后与前后缀进行或运算，取最大值。

网友提供了另一种基于位运算的解法，计算全体元素的或值，同时计算所有 bit 位上存在重复 1 的位置，通过异或运算将当前元素对或值的贡献抵消，然后补上重复位置上的 1。

代码

/**
 * @date 2025-03-21 0:08
 */
public class MaximumOr2680 {

    public long maximumOr_v1(int[] nums, int k) {
        int n = nums.length;
        int or = 0;
        int multiBits = 0;
        for (int i = 0; i < n; i++) {
            multiBits = multiBits | or & nums[i];
            or = or | nums[i];
        }
        long res = 0L;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, or ^ nums[i] | multiBits | ((long) nums[i] << k));
        }
        return res;
    }

    public long maximumOr(int[] nums, int k) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        int[] suffix = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] | nums[i - 1];
            suffix[n - i] = suffix[n - i + 1] | nums[n - i];
        }
        long res = 0L;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, prefix[i] | suffix[i + 1] | ((long) nums[i] << k));
        }
        return res;
    }

}

性能

目标

给你一个下标从 0 开始的整数数组 nums 。对于每个下标 i（1 <= i <= nums.length - 2），nums[i] 的 美丽值 等于：

• 2，对于所有 0 <= j < i 且 i < k <= nums.length - 1 ，满足 nums[j] < nums[i] < nums[k]
• 1，如果满足 nums[i - 1] < nums[i] < nums[i + 1] ，且不满足前面的条件
• 0，如果上述条件全部不满足

返回符合 1 <= i <= nums.length - 2 的所有 nums[i] 的 美丽值的总和 。

示例 1：

输入：nums = [1,2,3]
输出：2
解释：对于每个符合范围 1 <= i <= 1 的下标 i :
- nums[1] 的美丽值等于 2

示例 2：

输入：nums = [2,4,6,4]
输出：1
解释：对于每个符合范围 1 <= i <= 2 的下标 i :
- nums[1] 的美丽值等于 1
- nums[2] 的美丽值等于 0

示例 3：

输入：nums = [3,2,1]
输出：0
解释：对于每个符合范围 1 <= i <= 1 的下标 i :
- nums[1] 的美丽值等于 0

说明：

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

思路

有一个数组 nums，元素的美丽值定义如下：

• 如果 nums[i] > nums[j] && 0 =< j < i && nums[i] < nums[k] && i < k <= n - 1，美丽值为 2
• 如果 nums[i - 1] < nums[i] < nums[i + 1]，美丽值为 1
• 否则美丽值为 0

简单来说就是如果元素大于它前面的所有元素值并且小于它后面的所有元素值，美丽值为 2。如果仅仅大于它前面一个元素且小于它后面一个元素，美丽值为 1。

首先想到的是使用单调栈维护当前元素后面第一个 小于等于 它的元素下标，保存到 floor[i]，如果没有记录为 n；维护当前元素前面第一个 大于等于 它的元素下标，保存到 ceiling[i]，如果没有记录为 -1。当 floor[i] == n && ceiling[i] == -1 时，美丽值为 2，floor[i] > i + 1 && ceiling[i] < i - 1 时，美丽值为 1。

网友题解使用的是维护前缀最大值和后缀最小值，如果当前元素大于前面的最大值且小于后面的最小值，美丽值为 2，否则直接比较前后两个元素，如果满足条件，美丽值为 1。

代码

/**
 * @date 2025-03-11 8:48
 */
public class SumOfBeauties2012 {

    /**
     * 前缀最大值 后缀最小值
     */
    public int sumOfBeauties_v1(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n];
        int[] suffix = new int[n];
        suffix[n - 1] = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            prefix[i] = Math.max(prefix[i - 1], nums[i - 1]);
            suffix[n - 1 - i] = Math.min(suffix[n - i], nums[n - i]);
        }
        int res = 0;
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > prefix[i] && nums[i] < suffix[i]) {
                res += 2;
            } else if (nums[i] > nums[i - 1] && nums[i] < nums[i + 1]) {
                res++;
            }
        }
        return res;
    }

    /**
     * 单调栈
     */
    public int sumOfBeauties(int[] nums) {
        int n = nums.length;
        int[] floor = new int[n];
        int[] ceiling = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        int res = 0;
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                floor[stack.pop()] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            floor[stack.pop()] = n;
        }
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
                ceiling[stack.pop()] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            ceiling[stack.pop()] = -1;
        }
        for (int i = 1; i < n - 1; i++) {
            if (floor[i] == n && ceiling[i] == -1) {
                res += 2;
            } else if (floor[i] > i + 1 && ceiling[i] < i - 1) {
                res++;
            }
        }
        return res;
    }

}

性能