Given a m * n matrix of distinct numbers, return all lucky numbers in the matrix in any order.

A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

1
2
3
4
5
Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]

Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]

比赛一开始用了一个费力不讨好的办法:

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
class Solution {
    public List<Integer> luckyNumbers (int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return res;
        
        int m = matrix.length, n = matrix[0].length;
        
        Stack<Integer> min = new Stack<>();
        Stack<Integer> col = new Stack<>();
        
        for (int[] mat : matrix) {
            int minNum = mat[0];
            for (int i = 0; i < n; ++i) {
                if (minNum > mat[i]) minNum = mat[i];
            }
            min.push(minNum);
            
            for (int i = 0; i < n; ++i) {
                if (minNum == mat[i]) col.push(i);
            }
        } // min in each row, corresponding col
        
        while (!min.empty()) {
            int num = min.pop();
            int c = col.pop();
            System.out.println(num);
            System.out.println(c);
            
            for (int i = 0; i < m; ++i) {
                if (i != m-1 && num == matrix[i][c]) continue;
                if (num < matrix[i][c]) break;
                if (i == m-1 && num >= matrix[i][c]) res.add(num);
            }
        }
        
        return res;
    }
}

而实际上，只需注意到几个小点，就可以很简单写出来.

  1. 二维数组：拆分为2个一维数组，如果这两个一维数组分别是一个存储row min和column max;
  2. 因为每个数都是distinct，那么row min == column max的时候，就是这种lucky number;
  3. 如何把所有的row min和col max分别放到两个数组中？实际上，并不需要额外怎么样处理，就只是普通的遍历，只不过需要注意到遍历的顺序是什么样的: 内层for循环每次遍历完成，min[i]就完全得出来了，但是max[j]是只获得了一个数，然后外层for循环下一次的时候才会每个数都比较大小更新一次，所以遍历过程更新值的顺序是不同的；细细体会。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<Integer> luckyNumbers (int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        int[] mi = new int[m]; int[] mx = new int[n];
        Arrays.fill(mi, Integer.MAX_VALUE);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                mi[i] = Math.min(mi[i], matrix[i][j]);
                mx[j] = Math.max(mx[j], matrix[i][j]);
            }
        }
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mi[i] == mx[j]) 
                    res.add(mi[i]);
            }
        }
        
        return res;
    }
}