Sliding Window Maximum

Sliding Window Maximum
 avatar
user_4666436
java
2 years ago
1.9 kB
5
Indexable
Never
import java.io.*;
import java.util.*;

public class Main{
  

public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());
    int[] a = new int[n];
    for(int i = 0; i < n; i++){
       a[i] = Integer.parseInt(br.readLine());
    }
    int k = Integer.parseInt(br.readLine());

    Stack<Integer> max = new Stack<>();
    Stack<Integer> min = new Stack<>();
    
    max.push(0);
    
    for(int i=1;i<k;i++){
        if(a[max.peek()] < a[i]){
            max.push(i);
        }
        else{
            min.push(i);
        }
    }
    
    System.out.println(a[max.peek()]);
    
    for(int i=k;i<a.length;i++){
        if((i-max.peek())<k){
            if(a[max.peek()] > a[i]){
                System.out.println(a[max.peek()]);
                min.push(i);
            }
            else{
                max.push(i);
                System.out.println(a[max.peek()]);
            }
        }
        else{
            Stack<Integer> tmp = new Stack<>();
            max.clear();
            if(min.size() != 0){
                max.push(min.peek());
                min.pop();
            }
            while(min.size() != 0 && i-min.peek() < k){
                if(a[min.peek()] > a[i] && a[max.peek()] < a[min.peek()]){
                    max.push(min.peek());
                }
                else{
                    tmp.push(min.peek());
                }
                min.pop();
            }
            
            if(min.size() != 0 && i - min.peek() >= k){
                min.clear();
            }
            
            if(max.size() == 0 && min.size() == 0){
                max.push(i);
            }
            
            min = tmp;
            System.out.println(a[max.peek()]);
        }
    }
    
 }
}