1380. Lucky Numbers in a Matrix

Hint

class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& matrix)
    {
        // Get the dimensions of the matrix
        
        // Variable to store the maximum of all row minimums
        for ()
        {
            // Variable to store the minimum value in the current row
            for ()
            {
                // Update the row minimum value
            }
            // Update the maximum of row minimums
        }
        
        // Variable to store the minimum of all column maximums
        for ()
        {
            // Variable to store the maximum value in the current column
            for ()
            {
                // Update the column maximum value
            }
            // Update the minimum of column maximums
        }
        
        // Check if the maximum of row minimums is equal to the minimum of column maximums
        // If true, return the lucky number
        
        // If no lucky number is found, return an empty vector
    }
};

Solution

class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& matrix)
    {
        int m = matrix.size(), n = matrix[0].size();
        
        int rMinMax = INT_MIN;
        for (int i = 0; i < m; ++i)
        {

            int rMin = INT_MAX;
            for (int j = 0; j < n; ++j)
            {
                rMin = min(rMin, matrix[i][j]);
            }
            rMinMax = max(rMinMax, rMin);
        }
        
        int cMaxMin = INT_MAX;
        for (int i = 0; i < n; ++i)
        {

            int cMax = INT_MIN;
            for (int j = 0; j < m; j++)
            {
                cMax = max(cMax, matrix[j][i]);
            }
            cMaxMin = min(cMaxMin, cMax);
        }
        if (rMinMax == cMaxMin)
        {
            return {rMinMax};
        }
        return {};
    }
};

• 時間複雜度：
  $O(m\cdot n)$
• 空間複雜度：
  $O(1)$