跳转至

1594. 矩阵的最大非负积

题目描述

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

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

返回 最大非负积 对 109 + 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

解法

方法一：动态规划

我们定义一个三维数组 \(f\)，其中 \(f[i][j][0]\) 和 \(f[i][j][1]\) 分别表示从左上角 \((0, 0)\) 出发到达位置 \((i, j)\) 的路径中积的最小值和最大值。对于每个位置 \((i, j)\)，我们可以从上方 \((i - 1, j)\) 或左方 \((i, j - 1)\) 转移过来，因此我们需要考虑这两条路径的积的最小值和最大值与当前单元格的值相乘后的结果。

最后，我们需要返回 \(f[m - 1][n - 1][1]\) 对 \(10^9 + 7\) 取余的结果，如果 \(f[m - 1][n - 1][1]\) 小于 \(0\)，则返回 \(-1\)。

时间复杂度 \(O(m \times n)\)，空间复杂度 \(O(m \times n)\)。其中 \(m\) 和 \(n\) 分别是矩阵的行数和列数。

 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
class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        f = [[[0, 0] for _ in range(n)] for _ in range(m)]

        for i in range(m):
            for j in range(n):
                x = grid[i][j]
                if i == 0 and j == 0:
                    f[i][j][0] = x
                    f[i][j][1] = x
                    continue

                mn, mx = inf, -inf

                if i > 0:
                    a, b = f[i - 1][j]
                    mn = min(mn, a * x, b * x)
                    mx = max(mx, a * x, b * x)

                if j > 0:
                    a, b = f[i][j - 1]
                    mn = min(mn, a * x, b * x)
                    mx = max(mx, a * x, b * x)

                f[i][j][0], f[i][j][1] = mn, mx

        ans = f[m - 1][n - 1][1]
        mod = 10**9 + 7
        return -1 if ans < 0 else ans % mod

 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
class Solution {
    public int maxProductPath(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        long[][][] f = new long[m][n][2];

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                long x = grid[i][j];

                if (i == 0 && j == 0) {
                    f[i][j][0] = x;
                    f[i][j][1] = x;
                    continue;
                }

                long mn = Long.MAX_VALUE, mx = Long.MIN_VALUE;

                if (i > 0) {
                    long a = f[i - 1][j][0], b = f[i - 1][j][1];
                    mn = Math.min(mn, Math.min(a * x, b * x));
                    mx = Math.max(mx, Math.max(a * x, b * x));
                }

                if (j > 0) {
                    long a = f[i][j - 1][0], b = f[i][j - 1][1];
                    mn = Math.min(mn, Math.min(a * x, b * x));
                    mx = Math.max(mx, Math.max(a * x, b * x));
                }

                f[i][j][0] = mn;
                f[i][j][1] = mx;
            }
        }

        long ans = f[m - 1][n - 1][1];
        int mod = (int) 1e9 + 7;
        return ans < 0 ? -1 : (int) (ans % mod);
    }
}

 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
class Solution {
public:
    int maxProductPath(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<array<long long, 2>>> f(m, vector<array<long long, 2>>(n));

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                long long x = grid[i][j];
                if (i == 0 && j == 0) {
                    f[i][j] = {x, x};
                    continue;
                }

                long long mn = LLONG_MAX, mx = LLONG_MIN;

                if (i > 0) {
                    auto [a, b] = f[i - 1][j];
                    mn = min(mn, min(a * x, b * x));
                    mx = max(mx, max(a * x, b * x));
                }

                if (j > 0) {
                    auto [a, b] = f[i][j - 1];
                    mn = min(mn, min(a * x, b * x));
                    mx = max(mx, max(a * x, b * x));
                }

                f[i][j] = {mn, mx};
            }
        }

        long long ans = f[m - 1][n - 1][1];
        const int mod = 1e9 + 7;
        return ans < 0 ? -1 : ans % mod;
    }
};

 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
func maxProductPath(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    f := make([][][2]int64, m)
    for i := range f {
        f[i] = make([][2]int64, n)
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            x := int64(grid[i][j])
            if i == 0 && j == 0 {
                f[i][j] = [2]int64{x, x}
                continue
            }

            mn, mx := int64(1<<63-1), int64(-1<<63)

            if i > 0 {
                a, b := f[i-1][j][0], f[i-1][j][1]
                mn = min(mn, min(a*x, b*x))
                mx = max(mx, max(a*x, b*x))
            }

            if j > 0 {
                a, b := f[i][j-1][0], f[i][j-1][1]
                mn = min(mn, min(a*x, b*x))
                mx = max(mx, max(a*x, b*x))
            }

            f[i][j] = [2]int64{mn, mx}
        }
    }

    ans := f[m-1][n-1][1]
    mod := int64(1e9 + 7)
    if ans < 0 {
        return -1
    }
    return int(ans % mod)
}

 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
function maxProductPath(grid: number[][]): number {
    const m = grid.length,
        n = grid[0].length;
    const f = Array.from({ length: m }, () => Array.from({ length: n }, () => [0, 0]));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const x = grid[i][j];

            if (i === 0 && j === 0) {
                f[i][j] = [x, x];
                continue;
            }

            let mn = Infinity,
                mx = -Infinity;

            if (i > 0) {
                const [a, b] = f[i - 1][j];
                mn = Math.min(mn, a * x, b * x);
                mx = Math.max(mx, a * x, b * x);
            }

            if (j > 0) {
                const [a, b] = f[i][j - 1];
                mn = Math.min(mn, a * x, b * x);
                mx = Math.max(mx, a * x, b * x);
            }

            f[i][j] = [mn, mx];
        }
    }

    const ans = f[m - 1][n - 1][1];
    const mod = 1e9 + 7;
    return ans < 0 ? -1 : ans % mod;
}

 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
impl Solution {
    pub fn max_product_path(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut f = vec![vec![[0i64; 2]; n]; m];

        for i in 0..m {
            for j in 0..n {
                let x = grid[i][j] as i64;

                if i == 0 && j == 0 {
                    f[i][j] = [x, x];
                    continue;
                }

                let mut mn = i64::MAX;
                let mut mx = i64::MIN;

                if i > 0 {
                    let [a, b] = f[i - 1][j];
                    mn = mn.min(a * x).min(b * x);
                    mx = mx.max(a * x).max(b * x);
                }

                if j > 0 {
                    let [a, b] = f[i][j - 1];
                    mn = mn.min(a * x).min(b * x);
                    mx = mx.max(a * x).max(b * x);
                }

                f[i][j] = [mn, mx];
            }
        }

        let ans = f[m - 1][n - 1][1];
        let mod_val = 1_000_000_007i64;
        if ans < 0 {
            -1
        } else {
            (ans % mod_val) as i32
        }
    }
}

评论