SHARE
TWEET

Untitled

a guest Jan 24th, 2020 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution{
  2.     public int[]  maxSlidingWindow(int[] nums, int k) {
  3.         if (nums == null || nums.length == 0)
  4.             return new int[0];
  5.  
  6.         List<Integer> list = new ArrayList<>();
  7.         Deque<Node> deque = new ArrayDeque<>();
  8.         for (int i = 0; i < nums.length; i++) {
  9.             int curr = nums[i];
  10.             if (i >= k - 1) {
  11.                 int indexToRemove = i - (k - 1);
  12.                 addAndCompress(deque, Node.of(i, nums[i]));
  13.                 Node first = deque.getFirst();
  14.                 if (first.index == indexToRemove) deque.removeFirst();
  15.                 list.add(first.val);
  16.             } else {
  17.                 addAndCompress(deque, Node.of(i, curr));
  18.             }
  19.  
  20.         }
  21.  
  22.  
  23.         return toArray(list);
  24.     }
  25.  
  26.     private void addAndCompress(Deque<Node> deque, Node curr) {
  27.         if (deque.isEmpty()) {
  28.             deque.add(curr);
  29.             return;
  30.         }
  31.         while (true) {
  32.             if (deque.getLast().val <= curr.val) {
  33.                 deque.removeLast();
  34.  
  35.                 if (deque.isEmpty()) {
  36.                     deque.add(curr);
  37.                     return;
  38.                 }
  39.             }
  40.             else {
  41.                 deque.addLast(curr);
  42.                 return;
  43.             }
  44.         }
  45.     }
  46.  
  47.     static class Node {
  48.         int index;
  49.         int val;
  50.  
  51.         public Node(int index, int val) {
  52.             this.index = index;
  53.             this.val = val;
  54.         }
  55.  
  56.         static Node of (int index, int val) {
  57.             return new Node(index, val);
  58.         }
  59.     }
  60.  
  61.     private int[] toArray(List<Integer> list) {
  62.         int[] res = new int[list.size()];
  63.         for (int i = 0; i < list.size(); i++) {
  64.             res[i] = list.get(i);
  65.         }
  66.         return res;
  67.     }
  68.  
  69. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top