Indeed OA 18

我觉得这题的坑在于可能出现重复渲染。
所以，一个heap ＋ bfs会比较快些。bfs途中，也把点加到heap中，这样可以确保不会重复渲染。
有的类似Dijkstra的贪心

楼主这种方法后来我看有人说也是过不去，但是这个方法的时间复杂度还是O(Height*Width*n)么？空间复杂度是o(1)?

补充内容 (2018-10-16 13:38):
空间复杂度 O(H*W)

bingoleung26 发表于 2018-1-12 01:16
我test case过了，是用priority queue 做bfs，每次只dequeue 目前扩散的ink value最大那个queue，这样可以 ...

LZ能再详细解释解释吗？

楼主，你问答题，怎么improve，你写什么啊？

有点坑啊，这题，按照楼主的方法，复杂度感觉比pq要高啊，有重复染色的情况。 按理说用pq会保证每个点只会访问一次，不会重复访问

i think the reason is when you update the row and col with darkness then do recursion, will cut out more unnecessary updates... the 4 corners recursion is somehow like bounded  by the cross (imagine)

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies