领印面试难题

zyrnj 发表于 2023-8-28 13:45
记录最大值？leftmax，rightmax，topmax，bottommax

具体说说？而且刚加了更新

cougar 发表于 2023-8-28 13:45
具体说说？而且刚加了更新

我想的就是对每行都用数组记录这个位置从左边的最大值，还有从右边的最大值，就是一个m*n的记录数组，用m*n时间完成。再对每列也这样记录上下的最大值，也是mn。然后遍历每个位置，就可以O1得到这个位置的雨水了。
就是经典接雨水的解法2

zyrnj 发表于 2023-8-28 14:44
我想的就是对每行都用数组记录这个位置从左边的最大值，还有从右边的最大值，就是一个m*n的记录数组，用m ...

找完还要做一次bfs/dfs应该，相邻的水面应该是同一高度的，取一组connected的中的最小值。

震惊我司开始有external hiring opening了？估计是很高的level吧

匿名用户 发表于 2023-8-28 19:45
找完还要做一次bfs/dfs应该，相邻的水面应该是同一高度的，取一组connected的中的最小值。

这么做是不对的。我写了半天有些用例过不了。大家可以去看lc上的讨论。