标签： medium

目标

给你一个整数数组 nums。

如果满足 nums[i] == nums[j] == nums[k]，且 (i, j, k) 是 3 个 不同 下标，那么三元组 (i, j, k) 被称为 有效三元组 。

有效三元组 的 距离 被定义为 abs(i - j) + abs(j - k) + abs(k - i)，其中 abs(x) 表示 x 的 绝对值 。

返回一个整数，表示 有效三元组 的 最小 可能距离。如果不存在 有效三元组 ，返回 -1。

示例 1：

输入： nums = [1,2,1,1,3]
输出： 6
解释：
最小距离对应的有效三元组是 (0, 2, 3) 。
(0, 2, 3) 是一个有效三元组，因为 nums[0] == nums[2] == nums[3] == 1。它的距离为 abs(0 - 2) + abs(2 - 3) + abs(3 - 0) = 2 + 1 + 3 = 6。

示例 2：

输入： nums = [1,1,2,3,2,1,2]
输出： 8
解释：
最小距离对应的有效三元组是 (2, 4, 6) 。
(2, 4, 6) 是一个有效三元组，因为 nums[2] == nums[4] == nums[6] == 2。它的距离为 abs(2 - 4) + abs(4 - 6) + abs(6 - 2) = 2 + 2 + 4 = 8。

示例 3：

输入： nums = [1]
输出： -1
解释：
不存在有效三元组，因此答案为 -1。

说明：

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

思路

参考 3740.三个相等元素之间的最小距离I，数据范围变大了，当时写的就是 O(n) 的解法。

代码

/**
 * @date 2026-04-11 8:46
 */
public class MinimumDistance3740 {

    public int minimumDistance(int[] nums) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            map.putIfAbsent(nums[i], new ArrayList<>());
            map.get(nums[i]).add(i);
        }
        int res = Integer.MAX_VALUE;
        for (List<Integer> list : map.values()) {
            int size = list.size();
            if (size < 3) {
                continue;
            }
            for (int i = 2; i < size; i++) {
                res = Math.min(res, list.get(i) * 2 - list.get(i - 2) * 2);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

性能

目标

给你一个长度为 n 的整数数组 nums 和一个大小为 q 的二维整数数组 queries，其中 queries[i] = [li, ri, ki, vi]。

对于每个查询，按以下步骤执行操作：

• 设定 idx = li。
• 当 idx <= ri 时：
  • 更新：nums[idx] = (nums[idx] * vi) % (10^9 + 7)
  • 将 idx += ki。

在处理完所有查询后，返回数组 nums 中所有元素的 按位异或 结果。

示例 1：

输入： nums = [1,1,1], queries = [[0,2,1,4]]
输出： 4
解释：
唯一的查询 [0, 2, 1, 4] 将下标 0 到下标 2 的每个元素乘以 4。
数组从 [1, 1, 1] 变为 [4, 4, 4]。
所有元素的异或为 4 ^ 4 ^ 4 = 4。

示例 2：

输入： nums = [2,3,1,5,4], queries = [[1,4,2,3],[0,2,1,2]]
输出： 31
解释：
第一个查询 [1, 4, 2, 3] 将下标 1 和 3 的元素乘以 3，数组变为 [2, 9, 1, 15, 4]。
第二个查询 [0, 2, 1, 2] 将下标 0、1 和 2 的元素乘以 2，数组变为 [4, 18, 2, 15, 4]。
所有元素的异或为 4 ^ 18 ^ 2 ^ 15 ^ 4 = 31。

说明：

• 1 <= n == nums.length <= 10^3
• 1 <= nums[i] <= 10^9
• 1 <= q == queries.length <= 10^3
• queries[i] = [li, ri, ki, vi]
• 0 <= li <= ri < n
• 1 <= ki <= n
• 1 <= vi <= 10^5

思路

有一个长度为 n 的数组，对该数组执行 n 次查询，每次查询从 li 开始，对相距 ki 个位置上的元素执行 nums[idx] = (nums[idx] * vi) % (10^9 + 7) 直到下标 idx > ri。求处理完所有查询后 nums 中所有元素的 按位异或 结果。

查询次数最大为 10^3，每次查询区间也是 [0, 10^3 - 1]，步长 ki ∈ [1, 10^3]。

可以直接模拟。

代码

/**
 * @date 2026-04-08 8:56
 */
public class XorAfterQueries3653 {

    public int xorAfterQueries(int[] nums, int[][] queries) {
        int mod = 1000000007;
        for (int[] query : queries) {
            int li = query[0], ri = query[1], ki = query[2], vi = query[3];
            while (li <= ri) {
                nums[li] = (int) ((long) nums[li] * vi % mod);
                li += ki;
            }
        }
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }

}

性能

目标

给你一个在 XY 平面上的 width x height 的网格图，左下角 的格子为 (0, 0) ，右上角 的格子为 (width - 1, height - 1) 。网格图中相邻格子为四个基本方向之一（"North"，"East"，"South" 和 "West"）。一个机器人 初始 在格子 (0, 0) ，方向为 "East" 。

机器人可以根据指令移动指定的 步数 。每一步，它可以执行以下操作。

1. 沿着当前方向尝试 往前一步 。
2. 如果机器人下一步将到达的格子 超出了边界 ，机器人会 逆时针 转 90 度，然后再尝试往前一步。

如果机器人完成了指令要求的移动步数，它将停止移动并等待下一个指令。

请你实现 Robot 类：

• Robot(int width, int height) 初始化一个 width x height 的网格图，机器人初始在 (0, 0) ，方向朝 "East" 。
• void step(int num) 给机器人下达前进 num 步的指令。
• int[] getPos() 返回机器人当前所处的格子位置，用一个长度为 2 的数组 [x, y] 表示。
• String getDir() 返回当前机器人的朝向，为 "North" ，"East" ，"South" 或者 "West" 。

示例 1：

输入：
["Robot", "step", "step", "getPos", "getDir", "step", "step", "step", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
输出：
[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]

解释：
Robot robot = new Robot(6, 3); // 初始化网格图，机器人在 (0, 0) ，朝东。
robot.step(2);  // 机器人朝东移动 2 步，到达 (2, 0) ，并朝东。
robot.step(2);  // 机器人朝东移动 2 步，到达 (4, 0) ，并朝东。
robot.getPos(); // 返回 [4, 0]
robot.getDir(); // 返回 "East"
robot.step(2);  // 朝东移动 1 步到达 (5, 0) ，并朝东。
                // 下一步继续往东移动将出界，所以逆时针转变方向朝北。
                // 然后，往北移动 1 步到达 (5, 1) ，并朝北。
robot.step(1);  // 朝北移动 1 步到达 (5, 2) ，并朝 北 （不是朝西）。
robot.step(4);  // 下一步继续往北移动将出界，所以逆时针转变方向朝西。
                // 然后，移动 4 步到 (1, 2) ，并朝西。
robot.getPos(); // 返回 [1, 2]
robot.getDir(); // 返回 "West"

说明：

• 2 <= width, height <= 100
• 1 <= num <= 10^5
• step ，getPos 和 getDir 总共 调用次数不超过 10^4 次。

思路

有一个 w x h 的网格图，左下格子的坐标为 (0, 0)，初始时机器人朝向东方，机器人可以根据指令沿着当前朝向移动指定的步数，如果下一步到达了网格边界，则逆时针旋转 90° 继续尝试。实现 Robot 类，可以执行移动，以及获取机器人当前的位置、朝向。

暴力解法是模拟走每一步，如果越界则转向，直到剩余步数为 0。但是由于 step 调用次数最大为 10^4，所走步数是 int 类型，模拟走每一步会超时。

注意到机器人只能沿着网格的最外层绕圈，对周长 (w - 1 + h - 1)* 2 取模，只需模拟最后一圈即可。有一个出错点是回到原点的朝向，初始时朝向东方，回到原点时，朝向南方，需要特殊处理。

代码

/**
 * @date 2026-04-07 8:57
 */
public class Robot2069 {

    static class Robot {

        int[][] grid;
        int[][] directions = new int[][]{{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
        String[] res = new String[]{"South", "East", "North", "West"};
        int d = 1;
        int m;
        int n;
        int[] pos;

        public Robot(int width, int height) {
            m = height;
            n = width;
            grid = new int[m][n];
            pos = new int[]{0, 0};
        }

        public void step(int num) {
            int step = num % (m + n + m + n - 4);
            // 当位于原点，方向朝东时，再走 k 圈的方向应该朝南，如果不在原点的话，方向还是朝东
            if (step == 0 && d == 1 && pos[0] == 0 && pos[1] == 0) {
                d = 0;
            }
            while (step > 0) {
                while (pos[0] + directions[d][0] < 0
                        || pos[0] + directions[d][0] == n
                        || pos[1] + directions[d][1] < 0
                        || pos[1] + directions[d][1] == m
                ) {
                    d = ++d % 4;
                }
                pos[0] += directions[d][0];
                pos[1] += directions[d][1];
                step--;
            }
        }

        public int[] getPos() {
            return pos;
        }

        public String getDir() {
            return res[d];
        }
    }

}
/**
 * Your Robot object will be instantiated and called as such:
 * Robot obj = new Robot(width, height);
 * obj.step(num);
 * int[] param_2 = obj.getPos();
 * String param_3 = obj.getDir();
 */

性能

目标

机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ：

• -2 ：向左转 90 度
• -1 ：向右转 90 度
• 1 <= x <= 9 ：向前移动 x 个单位长度

在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点 obstacles[i] = (xi, yi) 。

机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，并继续执行下一个命令。

返回机器人距离原点的 最大欧式距离 的 平方 。（即，如果距离为 5 ，则返回 25 ）

注意：

• 北方表示 +Y 方向。
• 东方表示 +X 方向。
• 南方表示 -Y 方向。
• 西方表示 -X 方向。
• 原点 [0,0] 可能会有障碍物。

示例 1：

输入：commands = [4,-1,3], obstacles = []
输出：25
解释：
机器人开始位于 (0, 0)：
1. 向北移动 4 个单位，到达 (0, 4)
2. 右转
3. 向东移动 3 个单位，到达 (3, 4)
距离原点最远的是 (3, 4) ，距离为 3^2 + 4^2 = 25

示例 2：

输入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出：65
解释：机器人开始位于 (0, 0)：
1. 向北移动 4 个单位，到达 (0, 4)
2. 右转
3. 向东移动 1 个单位，然后被位于 (2, 4) 的障碍物阻挡，机器人停在 (1, 4)
4. 左转
5. 向北走 4 个单位，到达 (1, 8)
距离原点最远的是 (1, 8) ，距离为 1^2 + 8^2 = 65

示例 3：

输入：commands = [6,-1,-1,6], obstacles = []
输出：36
解释：机器人开始位于 (0, 0):
1. 向北移动 6 个单位，到达 (0, 6).
2. 右转
3. 右转
4. 向南移动 6 个单位，到达 (0, 0).
机器人距离原点最远的点是 (0, 6)，其距离的平方是 6^2 = 36 个单位。

说明：

• 1 <= commands.length <= 10^4
• commands[i] 的值可以取 -2、-1 或者是范围 [1, 9] 内的一个整数。
• 0 <= obstacles.length <= 10^4
• -3 10^4 <= xi, yi <= 3 10^4
• 答案保证小于 2^31

思路

二维平面的原点 (0, 0) 有一个机器人，开始时机器人面向北方。同时平面上还有一些障碍物 obstacles[i] = (xi, yi)。机器人可以根据指令 commands[i] 进行转向（-2 表示左转 90°，-1 表示右转 90°）或者向前移动对应数量的格子，如果碰到障碍物则在障碍物前停止，并继续执行下一条指令，返回机器人距离原点的最大欧式距离，坐标 (x, y) 距离原点的欧式距离为 x^2 + y^2。

由于机器人可能会往回走，最远的欧式距离可能在之前达到。

根据题目的指令描述模拟该过程，按照逆时针方向初始化上左下右四个方向的 (dx, dy)。初始方向 d = 0，左转时 d = (d + 1) % 4，右转时 d = (d + 3) % 4。为了判断下一格子是否有障碍物，可以使用哈希表 (rowi, coli_Set)保存障碍物的坐标。

网友题解是将坐标压缩到一个 int 中保存了，哈希表使用的是 Set<Integer>。由于坐标存在负值，这里还根据题目范围加了一个偏移量。

代码

/**
 * @date 2026-04-07 10:43
 */
public class RobotSim874 {

    public int robotSim(int[] commands, int[][] obstacles) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] o : obstacles) {
            map.putIfAbsent(o[0], new HashSet<>());
            map.get(o[0]).add(o[1]);
        }
        int res = 0;
        int[] pos = new int[]{0, 0};
        int[][] directions = new int[][]{{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
        int d = 0;
        for (int command : commands) {
            if (command == -1) {
                d = (d + 3) % 4;
            } else if (command == -2) {
                d = (d + 1) % 4;
            } else {
                while (command > 0) {
                    Set<Integer> set = map.get(pos[0] + directions[d][0]);
                    if (set != null &&
                            set.contains(pos[1] + directions[d][1])) {
                        break;
                    }
                    pos[0] += directions[d][0];
                    pos[1] += directions[d][1];
                    command--;
                }
                res = Math.max(res, pos[0] * pos[0] + pos[1] * pos[1]);
            }
        }
        return res;
    }

}

性能

目标

给你一个 m x n 的网格图，其中 (0, 0) 是最左上角的格子，(m - 1, n - 1) 是最右下角的格子。给你一个整数数组 startPos ，startPos = [startrow, startcol] 表示 初始 有一个 机器人 在格子 (startrow, startcol) 处。同时给你一个整数数组 homePos ，homePos = [homerow, homecol] 表示机器人的 家 在格子 (homerow, homecol) 处。

机器人需要回家。每一步它可以往四个方向移动：上，下，左，右，同时机器人不能移出边界。每一步移动都有一定代价。再给你两个下标从 0 开始的额整数数组：长度为 m 的数组 rowCosts 和长度为 n 的数组 colCosts 。

• 如果机器人往 上 或者往 下 移动到第 r 行 的格子，那么代价为 rowCosts[r] 。
• 如果机器人往 左 或者往 右 移动到第 c 列 的格子，那么代价为 colCosts[c] 。

请你返回机器人回家需要的 最小总代价 。

示例 1：

输入：startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7]
输出：18
解释：一个最优路径为：
从 (1, 0) 开始
-> 往下走到 (2, 0) 。代价为 rowCosts[2] = 3 。
-> 往右走到 (2, 1) 。代价为 colCosts[1] = 2 。
-> 往右走到 (2, 2) 。代价为 colCosts[2] = 6 。
-> 往右走到 (2, 3) 。代价为 colCosts[3] = 7 。
总代价为 3 + 2 + 6 + 7 = 18

示例 2：

输入：startPos = [0, 0], homePos = [0, 0], rowCosts = [5], colCosts = [26]
输出：0
解释：机器人已经在家了，所以不需要移动。总代价为 0 。

说明：

• m == rowCosts.length
• n == colCosts.length
• 1 <= m, n <= 10^5
• 0 <= rowCosts[r], colCosts[c] <= 10^4
• startPos.length == 2
• homePos.length == 2
• 0 <= startrow, homerow < m
• 0 <= startcol, homecol < n

思路

有一个 m x n 矩阵，其中有一个机器人在坐标 startPos，机器人家的坐标是 homePos，机器人可以上下左右移动，从上/下移动到第 i 行的成本为 rowCosts[i]，从左/右移动到第 j 列的成本为 colCosts[j]，求机器人回家需要的最小总代价。

根据题意代价均为非负数，只要不折返代价就是最小的，可以将横向与纵向移动分开考虑，分别计算 startPos[0] 到 homePos[0] 以及 startPos[1] 到 homePos[1] 的代价。

由于起点与家的相对位置是不确定的，循环的步长(+1 还是 -1)、结束条件(大于等于 还是 小于等于)需要动态定义。

网友题解则是直接减掉了起点的代价，统一由小坐标到大坐标累加成本。

代码

/**
 * @date 2026-04-07 11:21
 */
public class MinCost2087 {

    public int minCost(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts) {
        int res = 0;
        int sx = startPos[0];
        int sy = startPos[1];
        int hx = homePos[0];
        int hy = homePos[1];
        int dx = sx <= hx ? 1 : -1;
        int dy = sy <= hy ? 1 : -1;
        for (int i = sx + dx; dx == 1 ? i <= hx : i >= hx; i += dx) {
            res += rowCosts[i];
        }
        for (int i = sy + dy; dy == 1 ? i <= hy : i >= hy; i += dy) {
            res += colCosts[i];
        }
        return res;
    }

}

性能

目标

给你两个字符串 s1 和 s2 ，两个字符串长度都为 n ，且只包含 小写 英文字母。

你可以对两个字符串中的 任意一个 执行以下操作 任意 次：

选择两个下标 i 和 j ，满足 i < j 且 j - i 是 偶数，然后 交换 这个字符串中两个下标对应的字符。

如果你可以让字符串 s1 和 s2 相等，那么返回 true ，否则返回 false 。

示例 1：

输入：s1 = "abcdba", s2 = "cabdab"
输出：true
解释：我们可以对 s1 执行以下操作：
- 选择下标 i = 0 ，j = 2 ，得到字符串 s1 = "cbadba" 。
- 选择下标 i = 2 ，j = 4 ，得到字符串 s1 = "cbbdaa" 。
- 选择下标 i = 1 ，j = 5 ，得到字符串 s1 = "cabdab" = s2 。

示例 2：

输入：s1 = "abe", s2 = "bea"
输出：false
解释：无法让两个字符串相等。

说明：

• n == s1.length == s2.length
• 1 <= n <= 10^5
• s1 和 s2 只包含小写英文字母。

思路

有两个长度为 n 的字符串 s1 和 s2，判断能否通过操作使二者相等，每次操作交换下标之差为偶数的字母。

与 2839.判断通过操作能否让字符串相等I 相比，字符串长度由 4 变成了 n，操作的下标之差由 2 变成了偶数。

由于本身使用的就是一般解法，没有去特判具体的下标，可以复用之前的代码。

将字母根据下标分组，

代码

/**
 * @date 2026-03-30 15:41
 */
public class CheckStrings2840 {

    public boolean checkStrings(String s1, String s2) {
        int[][] chars = new int[2][26];
        int n = s1.length();
        for (int i = 0; i < n; i++) {
            chars[i % 2][s1.charAt(i) - 'a']++;
            chars[i % 2][s2.charAt(i) - 'a']--;
        }
        for (int[] ca : chars) {
            for (int c : ca) {
                if (c != 0) {
                    return false;
                }
            }
        }
        return true;
    }
}

性能

目标

给你一个由正整数组成的 m x n 矩阵 grid。你的任务是判断是否可以通过 一条水平或一条垂直分割线 将矩阵分割成两部分，使得：

• 分割后形成的每个部分都是 非空 的。
• 两个部分中所有元素的和 相等 。

如果存在这样的分割，返回 true；否则，返回 false。

示例 1：

输入： grid = [[1,4],[2,3]]
输出： true
解释：
在第 0 行和第 1 行之间进行水平分割，得到两个非空部分，每部分的元素之和为 5。因此，答案是 true。

示例 2：

输入： grid = [[1,3],[2,4]]
输出： false
解释：
无论是水平分割还是垂直分割，都无法使两个非空部分的元素之和相等。因此，答案是 false。

说明：

• 1 <= m == grid.length <= 10^5
• 1 <= n == grid[i].length <= 10^5
• 2 <= m * n <= 10^5
• 1 <= grid[i][j] <= 10^5

思路

有一个 m x n 矩阵，判断能否用一条水平线或者垂直线将矩阵分割成两部分，使得两部分的和相等，并且每一部分非空。

先求出总和，根据题意枚举所有分割水平线与垂直线判断两部分的和是否相等。

代码

/**
 * @date 2026-03-25 9:03
 */
public class CanPartitionGrid3546 {

    public boolean canPartitionGrid(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        long sum = 0L;
        for (int[] row : grid) {
            for (int num : row) {
                sum += num;
            }
        }
        if (sum % 2 == 1) {
            return false;
        }
        long half = sum / 2;
        long prefix = 0L;
        for (int i = 0; i < m - 1; i++) {
            for (int num : grid[i]) {
                prefix += num;
            }
            if (prefix << 1 == sum) {
                return true;
            } else if (prefix > half) {
                break;
            }
        }
        prefix = 0L;
        for (int j = 0; j < n - 1; j++) {
            for (int i = 0; i < m; i++) {
                prefix += grid[i][j];
            }
            if (prefix << 1 == sum) {
                return true;
            } else if (prefix > half) {
                break;
            }
        }
        return false;
    }

}

性能

目标

给你一个下标从 0 开始、大小为 n m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n m 的的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵 ：

• 对于每个元素 p[i][j] ，它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。

返回 grid 的乘积矩阵。

示例 1：

输入：grid = [[1,2],[3,4]]
输出：[[24,12],[8,6]]
解释：p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24
p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12
p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8
p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6
所以答案是 [[24,12],[8,6]] 。

示例 2：

输入：grid = [[12345],[2],[1]]
输出：[[2],[0],[0]]
解释：p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2
p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0 ，所以 p[0][1] = 0
p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0 ，所以 p[0][2] = 0
所以答案是 [[2],[0],[0]] 。

说明：

• 1 <= n == grid.length <= 10^5
• 1 <= m == grid[i].length <= 10^5
• 2 <= n * m <= 10^5
• 1 <= grid[i][j] <= 10^9

思路

已知 n x m 矩阵 grid，构造一个乘积矩阵 p 满足 p[i][j] 的值等于除了 grid[i][j] 外所有元素的乘积对 12345 取余。

计算所有元素的乘积会溢出，而保存取模后的乘积不支持除法。

---------
----X----
---------

实际上就是要快速计算出 - 的乘积。可以使用前后缀分解计算取模后的乘积。针对每一行进行前后缀分解，前缀的的最后一列以及后缀的第一列就是整行的乘积结果，对这 n 行整行的乘积再次进行前后缀分解。这样就可以快速求出 0 ~ i - 1 行的乘积，以及 i + 1 ~ n - 1 的乘积，然后对第 i 行，使用行的前后缀分解可以快速计算 grid[i][0 ~ j - 1] 以及 grid[i][j + 1 ~ m - 1] 的乘积。

代码

/**
 * @date 2026-03-24 8:57
 */
public class ConstructProductMatrix2906 {

    public int[][] constructProductMatrix(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int mod = 12345;
        int[][] prefix = new int[m][n + 1];
        int[][] suffix = new int[m][n + 1];
        for (int i = 0; i < m; i++) {
            prefix[i][0] = 1;
            suffix[i][n] = 1;
            for (int j = 0; j < n; j++) {
                prefix[i][j + 1] = (int) ((long) prefix[i][j] * grid[i][j] % mod);
                suffix[i][n - j - 1] = (int) ((long) suffix[i][n - j] * grid[i][n - j - 1] % mod);
            }
        }
        int[] rowPrefix = new int[m + 1];
        int[] rowSuffix = new int[m + 1];
        rowPrefix[0] = 1;
        rowSuffix[m] = 1;
        for (int i = 0; i < m; i++) {
            rowPrefix[i + 1] = (int) ((long) rowPrefix[i] * prefix[i][n] % mod);
            rowSuffix[m - i - 1] = (int) ((long) rowSuffix[m - i] * suffix[m - i - 1][0] % mod);
        }
        int[][] p = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                p[i][j] = (int) (((long) rowPrefix[i] * rowSuffix[i + 1] % mod) * ((long) prefix[i][j] * suffix[i][j + 1] % mod) % mod);
            }
        }
        return p;
    }

}

性能

目标

给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。

在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。

返回 最大非负积 对 10^9 + 7 取余 的结果。如果最大积为 负数 ，则返回 -1 。

注意，取余是在得到最大积之后执行的。

示例 1：

输入：grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1 。

示例 2：

输入：grid = [[1,-2,1],[1,-2,1],[3,-4,1]]
输出：8
解释：最大非负积对应的路径如图所示 (1 * 1 * -2 * -4 * 1 = 8)

示例 3：

输入：grid = [[1,3],[0,-4]]
输出：0
解释：最大非负积对应的路径如图所示 (1 * 0 * -4 = 0)

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 15
• -4 <= grid[i][j] <= 4

思路

有一个矩阵 grid，从左上角 (0, 0) 出发向右或向下移动到达 (m - 1, n - 1)。路径的乘积指路径经过的所有元素乘积，返回最大的非负乘积。

由于存在负值，总的最大非负路径可能由最小值与当前值相乘得到。

定义 dp[i][j][0] 表示到达 (i, j) 的最大路径积，dp[i][j][1] 表示到达 (i, j) 的最小路径积。状态转移方程为：

• dp[i][j][0] = Math.max(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]) 最小值与当前值相乘
• dp[i][j][0] = Math.max(dp[i][j][0], Math.max(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j])) 最大值与当前值相乘
• dp[i][j][1] = Math.min(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]) 最小值与当前值相乘
• dp[i][j][1] = Math.min(dp[i][j][1], Math.min(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j])) 最大值与当前值相乘

代码

/**
 * @date 2026-03-23 9:12
 */
public class MaxProductPath1594 {

    public int maxProductPath(int[][] grid) {
        int mod = 1000000007;
        int m = grid.length;
        int n = grid[0].length;
        long[][][] dp = new long[m][n][2];
        dp[0][0][0] = grid[0][0];
        dp[0][0][1] = grid[0][0];
        for (int j = 1; j < n; j++) {
            dp[0][j][0] = dp[0][j - 1][0] * grid[0][j];
            dp[0][j][1] = dp[0][j - 1][1] * grid[0][j];
        }
        for (int i = 1; i < m; i++) {
            dp[i][0][0] = dp[i - 1][0][0] * grid[i][0];
            dp[i][0][1] = dp[i - 1][0][1] * grid[i][0];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j][0] = Math.max(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]);
                dp[i][j][0] = Math.max(dp[i][j][0], Math.max(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j]));
                dp[i][j][1] = Math.min(dp[i - 1][j][1] * grid[i][j], dp[i][j - 1][1] * grid[i][j]);
                dp[i][j][1] = Math.min(dp[i][j][1], Math.min(dp[i - 1][j][0] * grid[i][j], dp[i][j - 1][0] * grid[i][j]));
            }
        }
        return dp[m - 1][n - 1][0] < 0 ? -1 : (int) (dp[m - 1][n - 1][0] % mod);
    }

}

性能

目标

给你一个 m x n 的整数矩阵 grid 和一个整数 k。

对于矩阵 grid 中的每个连续的 k x k 子矩阵，计算其中任意两个 不同值 之间的 最小绝对差 。

返回一个大小为 (m - k + 1) x (n - k + 1) 的二维数组 ans，其中 ans[i][j] 表示以 grid 中坐标 (i, j) 为左上角的子矩阵的最小绝对差。

注意：如果子矩阵中的所有元素都相同，则答案为 0。

子矩阵 (x1, y1, x2, y2) 是一个由选择矩阵中所有满足 x1 <= x <= x2 且 y1 <= y <= y2 的单元格 matrix[x][y] 组成的矩阵。

示例 1：

输入： grid = [[1,8],[3,-2]], k = 2
输出： [[2]]
解释：
只有一个可能的 k x k 子矩阵：[[1, 8], [3, -2]]。
子矩阵中的不同值为 [1, 8, 3, -2]。
子矩阵中的最小绝对差为 |1 - 3| = 2。因此，答案为 [[2]]。

示例 2：

输入： grid = [[3,-1]], k = 1
输出： [[0,0]]
解释：
每个 k x k 子矩阵中只有一个不同的元素。
因此，答案为 [[0, 0]]。

示例 3：

输入： grid = [[1,-2,3],[2,3,5]], k = 2
输出： [[1,2]]
解释：
    有两个可能的 k × k 子矩阵：
        以 (0, 0) 为起点的子矩阵：[[1, -2], [2, 3]]。
            子矩阵中的不同值为 [1, -2, 2, 3]。
            子矩阵中的最小绝对差为 |1 - 2| = 1。
        以 (0, 1) 为起点的子矩阵：[[-2, 3], [3, 5]]。
            子矩阵中的不同值为 [-2, 3, 5]。
            子矩阵中的最小绝对差为 |3 - 5| = 2。
    因此，答案为 [[1, 2]]。

说明：

• 1 <= m == grid.length <= 30
• 1 <= n == grid[i].length <= 30
• -10^5 <= grid[i][j] <= 10^5
• 1 <= k <= min(m, n)

思路

有一个 m x n 矩阵 grid，返回所有 k x k 子矩阵的最小绝对差，最小绝对差指矩阵中任意两个元素相减的差的绝对值。k x k 子矩阵以左上角为标识，将结果保存到二维矩阵中。

最小的绝对差一定在大小相邻的元素中产生，可以暴力枚举，使用有序集合保存子矩阵中的元素，然后遍历有序集合，记录相邻元素的绝对差取最小的即可。

代码

/**
 * @date 2026-03-20 11:11
 */
public class MinAbsDiff3567 {

    public int[][] minAbsDiff(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] res = new int[m - k + 1][n - k + 1];
        for (int[] row : res) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        for (int i = 0; i < m - k + 1; i++) {
            for (int j = 0; j < n - k + 1; j++) {
                TreeSet<Integer> set = new TreeSet<>();
                for (int x = i; x < i + k; x++) {
                    for (int y = j; y < j + k; y++) {
                        set.add(grid[x][y]);
                    }
                }
                if (set.size() <= 1) {
                    res[i][j] = 0;
                    continue;
                }
                Iterator<Integer> iterator = set.iterator();
                int prev = iterator.next();
                while (iterator.hasNext()) {
                    Integer cur = iterator.next();
                    res[i][j] = Math.min(res[i][j], Math.abs(cur - prev));
                    prev = cur;
                }
            }
        }
        return res;
    }

}

性能