改进寻找整数阵列子阵列最小值的算法。

Question

今年春天我为一家IT公司写了入学实习考试。有一个问题描述如下。我无法解决它，所以我需要帮助（目前我要通过新的测试，所以我需要分析我的错误）。我会很高兴的任何帮助。

输入：数组ARR N×整数编号，N的 - 长度ARR，以及数K（K < N）的问题的

声明：让我命名S_ARR （int i）：它的子阵列（长度K）为arr，其开始于arr [i]。

换句话说，S_ARR（ⅰ）是{arr [i], arr [i + 1], ... arr [i + K]}

对于偏移找到S_ARR的最小元件的所有容许的值（偏移）

的复杂性算法应该小于O（N * K）

输出：所有对（偏移，分钟（S_ARR（偏移））

实施例：

输入：arr = {4, 5 ,3, 3 ,2 ,7 , 1, 5, 9}, N = 9, K = 3

输出：

(0, 3) 
(1, 3) 
(2, 2) 
(3, 2) 
(4, 1) 
(5, 1) 
(6, 1) 

有关的详细信息S_ARR（ⅰ）（在这个例子中）：

s_arr(0) = {4, 5, 3} -> min = 3 
s_arr(1) = {5, 3, 3} -> min = 3 
s_arr(2) = {3, 3, 2} -> min = 2 
s_arr(3) = {3, 2, 7} -> min = 2 
s_arr(4) = {2, 7, 1} -> min = 1 
s_arr(5) = {7, 1, 5} -> min = 1 
s_arr(6) = {1, 5, 9} -> min = 1 

我的平凡解：

for(int i = 0; i < N - K; i++) 
    int min = arr[i]; 
    for(int j = 0; j < K; j++) 
     if (min > arr[i+j]) 
      min = arr[i+j]; 
    print("(" + i + "," + min + ")") 

显然，复杂度为O（ N * K）。应该做些什么来降低这种算法的复杂性？

Answer 1

您可以使用众所周知的滑动窗口最小化算法来实现O（N）复杂度。
这里是一篇关于它的文章：http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html

Answer 2

您应该使用您在前一个数组中已有的信息。如果前一个数组（i-1）的第一个元素不是较小的，那么可以简单地将最近一次迭代的最小值与当前数组的最后一个元素（i + k-1）进行比较。

希望有所帮助。