AcWing 1452. 寻找矩阵的极小值

// Forward declaration of queryAPI.
// int query(int x, int y);
// return int means matrix[x][y].

class Solution {
public:
    vector getMinimumValue(int n) {
        int l = 0, r = n - 1;
        typedef long long LL;
        const LL INF = 1e15;
        while(l < r){
            int mid = l + r >> 1;
            LL val = INF;
            int k;
            // 找这一列的最小值
            for(int i = 0; i < n; i++){
                int t = query(i, mid);
                if(val > t){
                    val = t;
                    k = i;
                }
            }
            // 然后判断最小值的左右两个数的大小
            LL left = mid ? query(k, mid - 1) : INF;
            LL right = mid ? query(k, mid + 1) : INF;
            // 如果最小值还小于左右两边的数,则是要求的极小值
            if(val < left && val < right) return {k, mid};
            if(left < val) r = mid - 1;
            else l = mid + 1;
        }
        // 如果上面没有返回,则还剩一下一列,该列的最小值则是要求的极小值
        
        LL val = INF;
        int k;
        // 找这一列的最小值
        for(int i = 0; i < n; i++){
            int t = query(i, r);
            if(val > t){
                val = t;
                k = i;
            }
        }
        return {k, r};
    }
};