在给定的数组段中查找最小数

Question

假设我们有一个很大的整数数组 A。我们想要回答许多查询，例如：

• 找到索引 0 和 100 之间的最小值

• 找到索引 4 和 90 之间的最小值

• ...

示例：A = {6, 1, 7, 5, 3}

• 索引 0 和 1 之间的最小值为 1

• 索引 2 和 3 之间的最小值为 5

• 索引 0 和 4 之间的最小值为 1

遍历每个查询的元素并找到最小值的明显方法在性能方面是不够的。我不知何故需要一次性存储所需的信息，然后在恒定时间内回答查询。所以算法不应该是二次的。需要比 O(N * M) 更好的东西。（N：数组大小，M：查询数）

我试过但找不到如何做到这一点。它一定是关于查找和存储一些总和并以某种方式使用它们的东西。有任何想法吗？谢谢阅读。

Answer 1

要考虑的两个选项：每个查询 O(n) 预计算和 O(logn)O(nlogn) 预计算和每个查询 O(1)第一种方法是通过递归计算偶数位置的所有对的最小值，然后在 4 的倍数位置处所有 4，然后在所有 8 的倍数处所有 8，依此类推。然后，每当您想要访问特定范围的最小值时，您将其分解为您已经拥有的部分并计算其中的最小值。例如，要找到元素 1..10 的最小值，请使用 1 和 2..3 和 4..7 以及 8..9 和 10 的最小值。第二个方法是计算所有位置的所有对的最小值，然后是所有位置的所有 4，然后是所有位置的所有 8。当你有一个特定的范围时，你将它构造为两个部分的最小值并计算这两个部分的最小值。例如，要找到元素 1..10 的最小值，请使用最小值 1..8 和最小值 3..10。

Answer 2

为每个问题制作一个“解决方案”、一个“最小值”和一个“最大值”然后，当您传递到数组的下一个元素时，如果您达到问题的 Index==min，则解决方案=该索引的数量。只要您没有达到最大值，您就可以将解决方案与该索引中的数字和实际解决方案进行比较。（好的，我在发布时意识到这是 n * m，抱歉）