华为OD机试C卷-- 最小矩阵宽度（Java & JS & Python & C）

题目：最小矩阵宽度

给定一个包含非负整数的二维矩阵，矩阵中的某个矩形区域的数字表示该区域的高度，请找出能包含至少一个水滴的最小矩形区域的宽度。

如果没有能包含水滴的区域，返回0。

示例 1：

输入： heights = [[1, 2, 5], [6, 4, 7], [8, 3, 6]]

输出： 2

示例 2：

输入： heights = [[1, 2, 5], [8, 3, 7], [5, 6, 4]]

输出： 1

示例 3：

输入： heights = [[1, 2, 5], [4, 3, 7], [8, 6, 6]]

输出： 0

提示：

1. 1 <= heights.length, heights[r].length <= 105
2. 0 <= heights[r][c] <= 107

来源：LeetCode

方法一：暴力法

public int minWidthArrow(int[][] heights) {
    int m = heights.length;
    int n = heights[0].length;
    int ans = Integer.MAX_VALUE;
 
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int minHeight = Integer.MAX_VALUE;
            for (int k = i; k < m; ++k) {
                for (int l = j; l < n; ++l) {
                    minHeight = Math.min(minHeight, heights[k][l]);
                    if (minHeight > heights[i][j]) {
                        ans = Math.min(ans, l - j + 1);
                        break;
                    }
                }
            }
        }
    }
 
    return ans == Integer.MAX_VALUE ? 0 : ans;
}

方法二：单调栈

public int minWidthArrow(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    int[][] next = new int[m][n];
    boolean[][] seen = new boolean[m][n];
    Queue<int[]> queue = new LinkedList<>();
 
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (seen[i][j]) continue;
            int h = heights[i][j];
            queue.offer(new int[]{i, j});
            seen[i][j] = true;
            while (!queue.isEmpty()) {
                int[] t = queue.poll();
                int ni = t[0], nj = t[1];
                for (int[] dir : new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
                    int nni = ni + dir[0], nnj = nj + dir[1];
                    if (nni >= 0 && nni < m && nnj >= 0 && nnj < n && !seen[nni][nnj]) {
                        if (heights[nni][nnj] >= h) {
                            next[nni][nnj] = nj - nj + 1;
                            queue.offer(new int[]{nni, nnj});
                            seen[nni][nnj] = true;
                        } else {
                            next[nni][nnj] = nj - nnj + 1;
                        }
                    }
                }
            }
        }