问题
题意不去过多比喻和解释了,就是求方阵中两点之间的路径中最大值的最小值(比如2x2矩阵一共有两条路径,第一条路径中最大值为3,第二天路径中最大值为2,那么结果就是2)
解决方案
- 想到用dp去解决这个问题,但是路径的选择其实是不具备dp条件的,即出了不能重复外,可以随便选择方向
- 思考路径的选择方法,发现可以在经过的路径的所有相邻点中,选择深度差最小的下一步,也就是使用一种类似贪心的方法
- 数据结构上,我们使用优先队列和集合,优先队列用于寻找贪心的下一个点,集合用于判断下一个点是否经过(其实也可以用布尔数组)
- 另一个方法思路很简单,就是二分猜测+DFS验证,时间复杂度也在O(N^2logN)这个数量级上
网友评论