其实直觉来看
就取个row的minimum与各col的maximum
如果这两个有交集就是答案了
肥肥智商大概只到这里
后来看别人讨论
发现这个lucky number最多只有一个
若存在两个lucky number的话 假设是(i0,j0)跟(i1,j1)位置
可以导出
M(i0,j0) > M(i1,j0) > M(i1,j1) > M(i0,j1) > M(i0,j0) -> 矛盾
所以不可能有两个lucky number
然后这个lucky number
也必然是 row minimums里面的maximum 以及 col maximums里面的minimum
若不是row minimums里面的maximum的话 假设是row minimums里面第二大的
代表那个column里的值 都是比这个第二大的值小
那就代表其他row有更小的值 然后就怎样怎样的我打不完了我要去上班了==
我就这样了
def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
mins_r = [min(r) for r in matrix]
mins_c = set()
for i in range(len(matrix[0])):
cur = 0
for j in range(len(matrix)):
cur = max(matrix[j][i], cur)
mins_c.add(cur)
# intersect
ans = []
for minr in mins_r:
if minr in mins_c:
ans.append(minr)
return ans