Saddleback搜索起始点选择：为何不从原点(0,0)采用双坐标递增搜索？

首先明确核心前提：Saddleback搜索的适用条件是函数f对两个参数都严格递增，即对任意x₁<x₂，都满足f(x₁,y) < f(x₂,y)；对任意y₁<y₂，都满足f(x,y₁) < f(x,y₂)，所有优化逻辑都围绕利用这个性质减少无效遍历展开。

为什么要做优化，从(0,0)原点开始搜索的问题 #

• 最初的暴力实现search f t = [(x,y) | x <- [0..t], y <- [0..t], t == f x y]时间复杂度为O(t²)，需要遍历从(0,0)到(t,t)的所有(t+1)²个点，当t取值较大时性能极速下降，完全无法实用。
• 从原点(0,0)出发的核心缺陷是无法利用f的严格递增性质做剪枝：如果当前点f(x,y) < t，你无法判断应该增大x还是增大y才能靠近目标值t，两个方向都会让f的结果变大，因此只能穷举所有可能的点，没有任何优化空间。

为什么采用x递增、y递减的路径，不能用双坐标同时递增的方向 #

一增一减路径的合理性 #

选择左上角(0,t)作为起点，配合x增y减的遍历逻辑，核心是每一步都可以直接排除一整行/一整列的无效点：

1. 若当前点f(x,y) < t：因为y固定时f随x递增，所以所有小于等于x的x'对应的f(x',y)都小于t，当前行y的左侧全部无效，直接x+1即可。
2. 若当前点f(x,y) > t：因为x固定时f随y递增，所以所有大于等于y的y'对应的f(x,y')都大于t，当前列x的上方全部无效，直接y-1即可。
3. 若当前点匹配目标t，记录结果后同时x+1、y-1即可，因为当前行和当前列都不可能再出现其他匹配点。

这种逻辑下每一步只会走x+1或者y-1，最多走2t步就能完成遍历，对应n×m矩阵的时间复杂度直接降到Θ(m+n)，和暴力实现的平方级复杂度有本质差距。
你提到的LeetCode上x递减y递增的实现逻辑完全一致，只是选择了另一个对角点作为起点，剪枝逻辑对应调整即可，核心原理没有区别。

双坐标同时递增的问题 #

如果采用x、y同时递增的遍历方向，会出现两个核心问题：

1. 无法做全行列剪枝：双增会让f的结果快速变大，既没法排除当前行的剩余点，也没法排除当前列的剩余点，必须分支遍历多个路径，反而会回到接近平方级的复杂度。
2. 容易漏过解：双增的步长如果控制不好，会直接跳过符合条件的点，反而需要额外的回溯逻辑，完全违背了Saddleback搜索线性复杂度的设计目标。

最终优化后的算法实现如下：

search f t = searchIn (0,t)
 where searchIn (x, y) | x>t || y<0 = []
                       | z<t = searchIn (x+1, y)
                       | z == t = (x, y):searchIn (x+1, y-1)
                       | z>t = searchIn (x,y-1)
  where z = f x y

内容的提问来源于stack exchange，提问作者Kareem Taha