AcWing 1452. 寻找矩阵的极小值 - python
原题链接
中等
作者:
浮槎_8
,
2024-04-14 11:30:27
,
所有人可见
,
阅读 1
python解法
class Solution(object):
def getMinimumValue(self, n):
"""
:type n: int
:rtype: List[int]
"""
l, r = 0, n - 1
while l < r:
mv = float('inf')
loc = 0
mid = l + (r - l) // 2
for i in range(n):
tmp = query(i, mid)
if tmp < mv:
loc = i
mv = tmp
lv = query(loc, mid - 1)
rv = query(loc, mid + 1)
if lv > mv and rv > mv: return [loc, mid]
if lv < mv:
r = mid - 1
else:
l = mid + 1
res = float('inf')
k = 0
# 这里去l对应的列找最小值也能ac
for i in range(n):
tmp = query(i, r) # or tmp = query(i, l)
if tmp < res:
k = i
res = tmp
return [k, r] # or return [k, l]