1

假设有一个 n × n 数组，其中 n 作为输入。数组中的数字也在输入中作为 n 行给出，每行有 n 个元素。此外，n 可以在 1 到 450 之间，并且数组中的每个数字（让我们将每个数字定义为 f(i,j) 可以在 1 到 200 之间。现在我们要找出有多少矩形子网格，使得f 的最小值正好是 88。所以程序应该找出这些子网格有多少。子网格可以只是一个元素，也可以是整个数组。

首先，我们知道任何给定数组中都有(n^2(n + 1)^2)/4 个子网格。找出一种使用有效算法编写此程序的方法。时间复杂度应低于 10^7，空间复杂度应低于 10^{10}。如您所见，它必须是一种有效的算法。（使用Java）

3 * 3 数组的一些示例输入是其中 n（在本例中为 3）是第一行，接下来的 n 行构成组成数组的 n 个数字：

|   2 |  36 |  56 |
|   5 |  88 |  90 |
| 100 | 150 | 200 |

数组图像在这里

那么输出将是：4

4

0 回答 0