其實直覺來看
就取個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