|
|
back to boardNice O(n) solution on java import java.io.*; import java.util.*; public class Main { private static final BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); private static final PrintWriter out = new PrintWriter(System.out); private static final StreamTokenizer tok = new StreamTokenizer(in); public static void main(String[] args) throws IOException { int windowSize = nextInt(); Queue<Integer> q = new LinkedList<Integer>(); Deque<Integer> maxQ = new LinkedList<Integer>(); while(true) { Integer n = nextInt(); if(n == -1) break; q.add(n); while((maxQ.isEmpty() == false) && (maxQ.peekLast() < n)) maxQ.removeLast(); maxQ.add(n); if(q.size() == windowSize) { Integer elemToRemove = q.remove(); Integer maxElement = maxQ.peek(); out.println(maxElement); if(maxElement == elemToRemove) maxQ.remove(); } } out.flush(); } private static int nextInt() throws IOException { if(tok.nextToken() != StreamTokenizer.TT_NUMBER) throw new IOException(); return (int)tok.nval; } } //note, though there's while loop to remove elements from maxQ, //amortized comlexity is still O(n) Re: Nice O(n) solution on java Posted by Tai Le 10 Aug 2013 14:31 It's quite a beautiful solution!! Tks you Re: Nice O(n) solution on java Posted by Egor 28 May 2017 16:29 Here is a c++ variation on this Java solution: int main() { int m; cin >> m; int n = 0; int a[25001] = {}; for (;; n++) { cin >> a[n]; if (a[n] == -1) break; } int r = 0; int max_a[25001] = {}; for (int i = 0; i < m - 1; i++, r++) { while (r - 1 >= 0 && max_a[r - 1] < a[i]) r--; max_a[r] = a[i]; } int l = 0; for (int i = m - 1; i < n; i++, r++) { while (r - 1 >= l && max_a[r - 1] < a[i]) r--; max_a[r] = a[i]; cout << max_a[l] << '\n'; int j = i - m + 1; if (a[j] == max_a[l]) l++; } } Note: I am not using any of the data structures |
|
|