题解 | #生成窗口最大值数组#

双端队列保存最大值的下标

这样做法，可以保证每个元素都只会在加入队列和移出队列的时候检查一次，时间复杂度能保证为 O(N)。效率表现优于下一种做法

算法表现

• 运行时间：2310ms，超过57.29% 用Java提交的代码
• 占用内存：163928KB，超过82.29%用Java提交的代码

import java.util.*;
import java.io.*;
   
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        Main mn = new Main();
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        String[] ss = sc.readLine().split(" ");
         
        int len = Integer.valueOf(ss[0]);
        int w = Integer.valueOf(ss[1]);
         
        ss = sc.readLine().split(" ");
        int[] data = new int[len];
        for(int i = 0; i < len; i++) {
            data[i] = Integer.valueOf(ss[i]);
        }
        int[] rtn = new int[len - w + 1];
         
        Deque<Integer> queue = new LinkedList<>();
         
         
        for(int i = 0; i < w-1; i++) {
            while(!queue.isEmpty() && data[i] >= data[queue.peek()]) {
                queue.pop();
            }
            queue.push(i);
        }
         
        int j = 0;
        int k = 0;
        for(int i = w-1; i < len; i++) {
            while(!queue.isEmpty() && data[i] >= data[queue.peek()]) {
                queue.pop();
            }
//             System.out.println("queue.size: " + queue.size() + ", index = " + i + ", w = " + w + ", cur = " + data[i]);
            queue.push(i);
            rtn[k++] = data[queue.peekLast()];
            if (j++ == queue.peekLast())
                queue.pollLast();
        }
        for (int i = 0; i < rtn.length; i++) {
            System.out.print(rtn[i] + " ");
        }
    }
}

双端队列保存窗口元素的值

这样做法，不能保证时间复杂度为 O(N)，不太好

算法表现

• 运行时间：2928ms，超过26.41% 用Java提交的代码
• 占用内存：178396KB，超过40.16%用Java提交的代码

import java.util.*;
import java.io.*;
  
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        Main mn = new Main();
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        String[] ss = sc.readLine().split(" ");
        
        int len = Integer.valueOf(ss[0]);
        int w = Integer.valueOf(ss[1]);
        
        ss = sc.readLine().split(" ");
        int[] data = new int[len];
        for(int i = 0; i < len; i++) {
            data[i] = Integer.valueOf(ss[i]);
        }
        int[] rtn = new int[len - w + 1];
        
        Deque<Integer> queue = new LinkedList<>();
        
        
        for(int i = 0; i < w-1; i++) {
            while(!queue.isEmpty() && data[i] > queue.peek()) {
                queue.pop();
            }
            while(queue.size() < (i+1)) {
                queue.push(data[i]);
            }
        }
        
        int j = 0;
        for(int i = w-1; i < len; i++) {
            while(!queue.isEmpty() && data[i] > queue.peek()) {
                queue.pop();
            }
//             System.out.println("queue.size: " + queue.size() + ", index = " + i + ", w = " + w + ", cur = " + data[i]);
            while(queue.size() < w) {
                queue.push(data[i]);
            }
            rtn[j++] = queue.pollLast();
        }
        for (int i = 0; i < rtn.length; i++) {
            System.out.print(rtn[i] + " ");
        }
    }
}