狗家新鲜面经

WarriorZ

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

a64663485

gqr1997 发表于 2019-11-28 09:38
每次边长都是从最大边长开始算，不用从1开始算，时间复杂度不到n^3

if a matrix contains all 1 elements, and K is 2. Is the complexity still O(n^3)?

snapboy · 2019-12-11 15:20:22

gqr1997 发表于 2019-11-28 09:38
每次边长都是从最大边长开始算，不用从1开始算，时间复杂度不到n^3

找边长的时候是不是可以用二分？
顺便恭喜lz，已加米

gqr1997 · 2019-12-11 15:28:27

snapboy 发表于 2019-12-11 15:20
找边长的时候是不是可以用二分？
顺便恭喜lz，已加米

我觉得可以

q4chu

snapboy 发表于 2019-12-11 15:20
找边长的时候是不是可以用二分？
顺便恭喜lz，已加米

但如果是non-negative直接sliding window就好了吧。二分nlogn反而更慢

好像理解错题意了，请无视我。