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

生成窗口最大值数组

http://www.nowcoder.com/practice/b316c7f9617744b98fa311ae29ac516c

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

这样做法,可以保证每个元素都只会在加入队列和移出队列的时候检查一次,时间复杂度能保证为 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] + " ");
        }
    }
}
全部评论

相关推荐

11-01 08:48
门头沟学院 C++
伤心的候选人在吵架:佬你不要的,能不能拿户口本证明过户给我。。球球了
点赞 评论 收藏
分享
10-14 13:25
已编辑
门头沟学院 C++
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务