1428. Leftmost Column with at Least a One

从右上往左下方向找边缘 O(m+n) time O(1) space
复杂度要不是m要不是n，最多是m+n

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * class BinaryMatrix {
 *   public:
 *     int get(int row, int col);
 *     vector<int> dimensions();
 * };
 */

class Solution {
public:
    int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
        const auto &dim = binaryMatrix.dimensions();
        int m = dim[0], n = dim[1];
        int res = -1, r = 0, c = n - 1;
        while (r < m && c >= 0) {
            if (binaryMatrix.get(r, c)) {
                res = c--;
            } else {
                ++r;
            }
        }
        return res;
    }
};

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * class BinaryMatrix {
 *   public:
 *     int get(int row, int col);
 *     vector<int> dimensions();
 * };
 */

class Solution {
public:
    int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
        const auto &dim = binaryMatrix.dimensions();
        int m = dim[0], n = dim[1];
        int res = n, r = 0, c = n - 1;
        while (r < m && c >= 0) {
            if (binaryMatrix.get(r, c)) {
                res = min(res, c);
                --c;
            } else {
                ++r;
            }
        }
        return res == n ? -1 : res;
    }
};