范围内的最小值

Question

我希望能够在某一范围内找到最小值。
我需要每次迭代数组吗？还是有其他动态方法可以使用？
假设我有一个输入数组：

index: 0 1 2 3 4 5 6 7
value: 1 4 6 1 6 7 2 3

然后我需要在区间 <a,b>（包括 a 和 b）中选择最小值。例如：

min(0,7) = 1
min(0,2) = 1
min(4,6) = 2
min(1,2) = 4

我对最快的解决方案感兴趣，最好能在恒定时间内得到结果。

数组在此期间不会改变。

- noisy cat

---

似乎你只需要一个for循环。 - LeeNeverGup

这是线性的... 难道不能更快吗？ - noisy cat

你可以在O(N^2)的时间内为每个可能的范围预先计算结果。之后，查找将是常数时间。根据您需要多频繁地查找相同的数据，您可以分摊初始成本。 - Igor Tandetnik

数值没有排序。你确定你能使用二分查找吗？ - noisy cat

@kittyPL - 你不能在未排序的范围上进行二分查找。 - Peter R

Answer 1

如果您要对同一组数字执行多个查询，则需要构建一个笛卡尔树。

笛卡尔树可用作区间最小值查询的高效数据结构的一部分，这是一个涉及查询原始序列连续子序列中的最小值的区间搜索问题。

正如文章所说，可以在常数时间内执行查询。

- Peter Alexander

---

结构不错，但我不确定查询如何在常数时间内执行。如果深度为D，则O(D)也许不会让我感到惊讶...但是常数似乎有点勉强了。在原始文章中，如果我要求在9到18的范围内找到最小值（即1），它似乎需要比确定[12,10,20,15]中的最小值10所需的时间更长。 - Matthieu M.

@MatthieuM：这很棘手。查找涉及到在树中找到查询的边界节点的最近公共祖先。简单实现的时间复杂度是O(D)，正如您所预期的那样，但有一些技巧可以在O(1)中找到LCA，请参见http://en.wikipedia.org/wiki/Lowest_common_ancestor。 - Peter Alexander

Answer 2

你可以使用线段树解决这个问题。这篇文章是关于线段树和区间最小值查询的最佳教程之一。

我提供了JAVA实现，代码本身很清楚，请让我知道你是否有任何疑问。

public class SegmentTree {

    private int[] array;
    private int length;

    public static SegmentTree initialize(int[] a) {
        return new SegmentTree(a);
    }

    private SegmentTree(int[] a) {
        length = a.length - 1;
        int l = (int) (Math.log(a.length) / Math.log(2));
        l = (int) (Math.pow(2, l + 1) * 2 - 1);
        array = new int[l];
        initialize(a, 0, a.length - 1, 0);
    }

    private int initialize(int[] a, int p, int r, int index) {
        if (p == r) {
            array[index] = a[p];
            return a[p];
        }
        int q = p + (r - p) / 2;
        array[index] = Math.min(initialize(a, p, q, 2 * index + 1), initialize(a, q + 1, r, 2 * index + 2));
        return array[index];
    }

    public int findMin(int p, int r) {
        return _findMin(p, r, 0, length, 0);
    }

    private int _findMin(int qs, int qe, int ss, int se, int i) {
        if (qs <= ss && se <= qe) {
            return array[i];
        }
        if (qs > se || qe < ss) {
            return Integer.MAX_VALUE;
        }
        int q = ss + (se - ss) / 2;
        return Math.min(_findMin(qs, qe, ss, q, 2 * i + 1), _findMin(qs, qe, q + 1, se, 2 * i + 2));
    }

    private void print() {
        int index = 0;
        for (int k : array) {
            System.out.println(index + ":" + k);
            index++;
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 34, 5, 6, 78, 5, 67, 89};
        SegmentTree s = initialize(a);
        System.out.println(s.findMin(2, 4));
    }
}

- Trying

---

阅读了这篇文章后，代码变得容易理解了。然而，在解释时将变量命名为“qs、qe、ss、q”并不是一个好主意（我也喜欢简单函数的短名称）。此外，注释会很有帮助。无论如何，感谢这个对数解决方案，+1 :) - noisy cat

Answer 3

你可以尝试以下方法（不确定是否遗漏了什么）：

如果允许进行一些预处理，那么可以有一个局部最小值（谷底）的数组。

该数组应按照相应的索引排序。

一旦获得一个区间，就在最小值数组中执行较低索引的二分搜索。选择其中较大的一个。假设为I1。

然后，在最小值数组中执行较高给定索引的二分搜索。选择其中较小的一个。假设为I2。

如果I2 >= I1，则至少存在一个局部最小值在该区间内。只需比较该区间内的最小值和边界处的值即可得到答案。

否则，该区间内不存在局部最小值。在这种情况下，最小值将位于区间的边界上。只需比较两个值并获取较低的值即可。

- Abhishek Bansal

Answer 4

这是一个标准任务。您可以使用std库功能。它应该是最快的。来自这里的示例：

#include <iostream>     // std::cout
#include <algorithm>    // std::min_element, std::max_element

int main () {
  int myints[] = {3,7,2,5,6,4,9};

  std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << '\n';

  return 0;
}

---

顺便说一句，你无法在常数时间内获得结果，因为如果你需要在N个元素之间找到最小值，你需要检查每个元素。最小任务复杂度为O（N）。

- klm123

---

线性解法。如果可能的话，我想问一下是否有更快的方法。 - noisy cat

好的。如果有更快的东西，它将会在标准库中。 - klm123

这取决于情况。也许有一种动态的解决方案。据我所知，在标准库中并不常见。 - noisy cat

无论如何，它都不能比线性更快，您至少需要检查每个元素一次。 - klm123

当然不是。您可以预先生成一些辅助数组，然后使用它们在更短的时间内进行答案。请阅读有关前缀和的内容。http://en.wikipedia.org/wiki/Prefix_sum - noisy cat