我在寻找一个算法，找到所有鞍点的位置在一个nxn矩阵。
搜索stackoverflow上的其他答案，以及一般的其他站点，我只找到了在一个方向上操作的鞍点的解决方案。也就是说，我想找到一个鞍点，它可以是它的行中的最大值和它的列中的最小值，或者它的行中的最小值和列中的最大值。
例如，给定：
array = {
{ 10, 15, 20, 15, 10 }
{ 5, 10, 15, 10, 5 }
{ 0, 5, 10, 5, 0 }
{ 5, 10, 15, 10, 5 }
{ 10, 15, 20, 15, 10 } },
鞍点是角的10个，中间的10个。
我可以很容易地天真地找到它们，但我想要更有效率的东西。我被告知可以在O（n^2）内完成。
我想也许我可以修正X坐标，并通过Y坐标迭代来寻找所有的最大值和最小值，然后通过固定y坐标和迭代通过x坐标来反转这个过程，但是我不能很好地可视化它来实现这个想法。
任何帮助都将不胜感激。
最佳答案
请注意，在天真的实现O（N3）中，您正在重新计算一行/列中的每个元素的最大值和最小值。
为了消除这种低效性，其思想是遍历每个行和列，并在一个单独的n×n数组中标记所有位置的最大值和最小值。这个独立数组的每个元素都包含两个布尔信息：isMax和isMin（如果需要，可以将其编码为位）。如果行/列中的所有元素都是相同的（即最大值＝最小值），则可能不希望标记任何元素。
对于每一行/列，这可以在o（n）时间内完成。使用一个数组来记录当前最大值（最小值）的索引，如果数组中的值大于当前最大值（最小值），则清除数组。完成循环后，使用最大（最小）索引数组中的信息来标记nxn数组中对应的isMax（isMin）字段。
因为有n行和n列，所以这个步骤的复杂性是O（n2）。
剩下的就是遍历n x n数组，这个数组标记为搜索设置了isMax和isMin的任何位置。