Max Min Path

给一个int[][]的matirx，对于一条从左上到右下的path，path[i]中的最小值是min[i]，求所有min[]中的最大值。只能往下或右.
比如：

[8, 4, 7]
[6, 5, 9]
有3条path：
8-4-7-9 min: 4
8-4-5-9 min: 4
8-6-5-9 min: 5
return: 5
文／白马书院的姑娘（简书作者）
原文链接：http://www.jianshu.com/p/7f268597717b
著作权归作者所有，转载请联系作者获得授权，并标注“简书作者”。

/**
 * Created by RuiG on 11/20/16.
 */
public class PathMinMax {
    public static void main(String[] args) {
        PathMinMax test = new PathMinMax();
        int[][] matrix = {{8,4,7}, {6,5,9}};
        int[] ans = new int[1];
        test.dfs(matrix, Integer.MAX_VALUE, 0, 0, ans);
        System.out.println("min max dfs: " + ans[0]);
        System.out.println("min max dp: " + findPathMinMax(matrix));
    }


    public static int findPathMinMax(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return -1;
        }
        int m = matrix.length, n = matrix[0].length;
        int[] dp = new int[n];
        // build dp for first row
        dp[0] = matrix[0][0];
        for (int j = 1; j < dp.length; j++) {
            dp[j] = Math.min(dp[j - 1], matrix[0][j]);
        }
        // build dp for other rows
        for (int i = 1; i < m; i++) {
            dp[0] = Math.min(dp[0], matrix[i][0]);
            for (int j = 1; j < n; j++) {
                // 如果当前值比两条通路的最小值都大,那么选择其中大者
                if (matrix[i][j] > dp[j - 1] && matrix[i][j] > dp[j]) { 
                    dp[j] = Math.max(dp[j - 1], dp[j]);
                } else {
                    dp[j] = matrix[i][j];
                }
            }
        }

        return dp[n - 1];
    }

    public void dfs(int[][] matrix, int curMin, int i, int j, int[] max) {
        int m = matrix.length, n = matrix[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n) return;

        curMin = Math.min(curMin, matrix[i][j]);

        // reach bottom right
        if (i == m - 1 && j == n - 1) {
            max[0] = Math.max(max[0], curMin);
            return;
        }

        dfs(matrix, curMin, i + 1, j, max);
        dfs(matrix, curMin, i, j + 1, max);
    }

}