在给定的 $n \times n$ 矩阵 $A$ 中，鞍点是指在其所在行中为最大值且在其所在列中为最小值的元素。如果该元素的行或列中没有其他元素具有相同值，则称其为严格鞍点。寻找非严格鞍点在最坏情况下需要 $\Theta(n^2)$ 次矩阵查询，而严格鞍点只需 $O(n)$ 次查询即可找到。
1991年，Bienstock、Chung、Fredman、Schäffer、Shor 和 Suri，以及独立的 Byrne 和 Vaserstein 证明了可以在 $O(n \log n)$ 时间内使用 $O(n)$ 次矩阵查询来找到严格鞍点（或证明其不存在）。2024年，Dallant、Haagensen、Jacob、Kozma 和 Wild 提出了一个 $O(n \log^* n)$ 时间的算法，随后又出现了一个以高概率在 $O(n)$ 时间内运行的最优随机算法。然而，是否可以通过确定性方法达到 $O(n)$ 时间的目标仍然是一个未解的问题。
在此，我们通过提出一个简单的确定性算法解决了这个问题，该算法以最优的 $O(n)$ 时间找到严格鞍点，或报告其不存在。我们的算法结合了先前方法中的基本成分，以及从已排序列表集合中进行线性时间选择的技术。