fork download
copy 
  1.  
  2.  
  3. import java.util.ArrayDeque;
  4. import java.util.Queue;
  5.  
  6. /**
  7.  * Created by Vikrant on 4/1/14.
  8.  */
  9. public class Main {
  10. 	ArrayDeque<Integer> queue;
  11. 	Queue<Integer> save;
  12.  
  13. 	public static void main(String[] args) {
  14. 		Main sw = new Main();
  15. 		int[] A = new int[]{1, 7, 2, 3, 1, 4, 5, 2, 3, 6};
  16. 		int k = 3;
  17. 		sw.printKMax(A, k);
  18. 		k = 4;
  19. 		sw.printKMax(A, k);
  20. 		k = 1;
  21. 		sw.printKMax(A, k);
  22. 		k = A.length;
  23. 		sw.printKMax(A, k);
  24. 	}
  25.  
  26. 	public void printKMax(int[] A, int k) {
  27. 		solve(A, k);
  28. 		for (Integer e : save) {
  29. 			System.out.print(e + " ");
  30. 		}
  31. 		System.out.println();
  32. 	}
  33.  
  34. 	private void solve(int[] A, int k) {
  35. 		save = new ArrayDeque<Integer>();
  36. 		queue = new ArrayDeque<Integer>();
  37. 		for (int i = 0; i < k; i++) {
  38.  
  39. 			removeSmallerFromLast(A, i);
  40. 			queue.addLast(i);
  41. 		}
  42. 		for (int i = k; i < A.length; i++) {
  43. 			save.add(A[queue.getFirst()]);
  44.  
  45. 			// remove elements out of window
  46. 			while (!queue.isEmpty() && queue.getFirst() <= i - k)
  47. 				queue.pollFirst();
  48.  
  49. 			removeSmallerFromLast(A, i);
  50.  
  51. 			queue.addLast(i);
  52.  
  53. 		}
  54. 		save.add(A[queue.getFirst()]);
  55.  
  56. 	}
  57.  
  58. 	private void removeSmallerFromLast(int[] A, int i) {
  59. 		while (!queue.isEmpty() && A[queue.peekLast()] < A[i])
  60. 			queue.pollLast();
  61. 	}
  62.  
  63. }
  64.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
7 7 3 4 5 5 5 6 
7 7 4 5 5 5 6 
1 7 2 3 1 4 5 2 3 6 
7
https://ideone.com/83yTvU
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!