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

题目描述：

给定一个矩阵，矩阵中的每个元素都是正整数，你可以从矩阵中选择一个子矩阵，这个子矩阵的每一列的数字都是递增的，子矩阵的宽度称为最小矩阵宽度。

请设计一个算法，找到子矩阵的最小矩形宽度。

输入：

输入包含多个测试用例，每个测试用例以矩阵的形式给出。

输出：

对于每个测试用例，输出最小矩形宽度。

解决方案：

对于每一列，我们需要找到第一个比它大的数字。如果没有，那么宽度为1；如果有，则宽度为两者之间的距离加一。我们可以使用单调递增栈来实现这个功能。

以下是使用单调栈解决这个问题的代码示例：

Java版本：

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int rows = scanner.nextInt();
            int cols = scanner.nextInt();
            int[][] matrix = new int[rows][cols];
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    matrix[i][j] = scanner.nextInt();
                }
            }
            System.out.println(minMatrixWidth(matrix));
        }
        scanner.close();
    }
 
    public static int minMatrixWidth(int[][] matrix) {
        int n = matrix.length;
        int[][] nextGreater = new int[n][n];
        for (int i = 0; i < n; i++) {
            Stack<Integer> stack = new Stack<>();
            for (int j = 0; j < n; j++) {
                while (!stack.isEmpty() && matrix[stack.peek()][i] >= matrix[j][i]) {
                    stack.pop();
                }
                nextGreater[j][i] = stack.isEmpty() ? -1 : stack.peek();
                stack.push(j);
            }
        }
 
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (nextGreater[j][i] != -1) {
                    ans = Math.min(ans, nextGreater[j][i] - j + 1);
                }
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

JavaScript版本：

function minMatrixWidth(matrix) {
    let n = matrix.length;
    let nextGreater = new Array(n).fill(0).map(() => new Array(n).fill(-1));
    for (let i = 0; i < n; i++) {
        let stack = [];
        for (let j = 0; j < n; j++) {
            while (stack.length && matrix[stack[stack.length - 1]][i] >= matrix[j][i]) {
                stack.pop();
            }
            nextGreater[j][i] = stack.length === 0 ? -1 : stack[stack.length - 1];
            stack.push(j);
        }
    }
 
    let ans = Infinity;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {