给定数组A和数K，创建数组B，其中B [i] = min（A [i]，A [i + 1] .. A [i + K-1]）

David 发表于 Dev

大卫

给定一个整数数组A和一个整数值K，创建array B，其中B[i]是子数组中的最小值A[i], A[i+1], ..., A[i+K-1]。请注意，B.length它将等于A.length - K。

例如K = 3和A=[1,2,3,4,0,1,2]解决方案是B=[1,2,0,0,0]。

A  =  [1,2,3,4,0,1,2]
       _____| | | | |      
B[1] = 1      | | | | 
         _____| | | | 
B[2] =   2      | | | 
           _____| | | 
B[3] =         0  | | 
             _____| | 
B[4] =         0    | 
               _____| 
B[5] =         0

O（kn）时间复杂度的解决方案如下：

public static int[] createArray(int[] arr, int k) {
    int[] result = new int[arr.length];
    for (int i = 0; i <= arr.length - k; i++) {
        int curSmallestVal = arr[i];
        for (int j = i + 1; j < i + k; j++) {
            curSmallestVal = Math.min(curSmallestVal, arr[j]);
        }
        result[i] = curSmallestVal;
    }

    return result;
}

可以使用O（n）运行时提供更优雅的解决方案吗？（可能使用队列）

使用O（n）解决方案进行更新：

public static int[] getMinSlidingWindow(int[] arr, int k) {
    int[] result = new int[arr.length-k+1];
    Deque<Integer> queue = new LinkedList<Integer>();
    //initialize sliding window
    for (int i = 0; i < k; i++) {
        if (!queue.isEmpty() && arr[queue.getLast()] >= arr[i])
            queue.removeLast();
        queue.addLast(i);
    }

    for (int i = k; i < arr.length; i++) {
        result[i-k] = arr[queue.getFirst()];
        while (!queue.isEmpty() && arr[queue.getLast()] >= arr[i])
            queue.removeLast();
        queue.addLast(i);
        while (!queue.isEmpty() && queue.getFirst() <= i-k)
            queue.removeFirst();
    }

    result[arr.length-k] = arr[queue.removeFirst()]; 

    return result;
}

热切的俄语

使用双端队列（该队列支持从正面和背面添加推入和弹出），可以使用一些额外的逻辑来构造运行O（n）的解决方案。

这是解决方案的伪代码。

void getMaxSlidingWindow(int[] A, int k) {
    int[] B = new int[A.length - k];
    // Store the indexes of A in Q
    // Q.front(): index of smallest element in the window, Q.back(): index of the largest one in the window
    DobuleEndedQueue<int> Q = new DobuleEndedQueue<int>(); 

    for(int i=0; i<k; i++) {
       // Fill up the double ended queue for the first k elements
       // Remove elements that we would ignore because they're bigger than the next one in the window
       while(!Q.empty() && A[i] <= A[Q.back()]) {
          Q.popBack();
       }
       Q.pushBack(i);
    }

     for(int i=k; i < A.length; i++) {
       B[i - k] = A[Q.front()]; // The first element in the queue is the index of the smallest element in the window
       // Add the current element to the queue. Before we do, remove all elements that we would ignore immediately because they're bigger than the current one
       while(!Q.empty() && A[i] <= A[Q.back()]  ) {
          Q.popBack();
       }
       Q.pushToBack(i);
       // Remove any index from the front of the queue which is no longer in the window
       while(!Q.empty() && Q.front() <= i-k) {
         Q.popFront();
       }
    }
    B[A.length - k] = A[Q.front()];
}

该解决方案的时间复杂度为O（n）：我们对所有元素进行一次迭代，然后一次将其添加或删除到双端队列中。完成的最大运算为2n，这是O（n）复杂度。

为了使该解决方案起作用，您需要使用以下操作来实现双头队列数据结构：

class DobuleEndedQueue
int front(), void pushFront(int n), void popFront() // peeks at the front element, adds and removes to the front
int back(), void pushBack(int n) , void popBack() // same for the back element

通过一个简单的示例进一步说明该算法：

循环访问前k个元素，并将它们作为索引插入到双端Q数据结构中，以便A [Q.front（）]是窗口中的最小元素，而A [Q.back（）]是窗口中的最大元素。
当我们建立窗口时，请从此队列中丢弃“不必要的”元素：既不会计数的最小元素，也包括在窗口之外的元素
建立A = [8、6、9、2]和k-3的队列的示例
1. Q = [0]，（将0插入Q的后面，因为A [0]是我们看到的最小元素。）
1. Q = [1]，（A [1] <Q.back（）因此弹出back元素并替换为1。之所以这样做，是因为从现在开始寻找最小的数字时A [0]将是无关紧要的。）
1. Q = [1，2]，B = [8]（A [2]> Q.back（），因此我们在Q上加上2。B [0]将是Q中最小的项，即A [Q.first（）]，即A [1]）
1. Q = [3]，B = [8，2]（A [4]小于Q中的所有元素，因此我们将其全部弹出。B[1]将是Q中最小的元素，A [Q.first （）]，即A [3]