Simple Java Solution


  • 0
    Z
     
    public class Solution {
        public int[] maxSlidingWindow(int[] a, int k) {
            if (a == null || a.length == 0 || k <= 0) {
                return new int[0];
            }
    
            int size = a.length - k + 1;
            int[] result = new int[size];
            int index = 0;
            LinkedList<Integer> queue = new LinkedList<>();
            for (int i = 0; i < a.length; i++) {
                //删除过期数据,保证队列中存储的下标是当前窗口中的,即[i-k+1,i]
                while (!queue.isEmpty() && queue.peek() < i - k + 1) {
                    queue.poll();
                }
                //上面删除了窗口前面的数据,这时队列中保存的是当前窗口中数值递减的数据下标,每个a[i]都从队列后面往前冲,把比自己小的删掉,找到合适的位置,冲到最前面的话,队列只剩a[i],那么它就是当前窗口的最大值
                while (!queue.isEmpty() && a[queue.peekLast()] <= a[i]) {
                    queue.pollLast();
                }
                queue.offer(i);
                if (i - k + 1 >= 0) {
                    result[index] = a[queue.peek()];
                    index++;
                }
            }
            return result;
        }
    
        public static void main(String[] args) {
            int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
            int k = 3;
            int[] result = new Solution().maxSlidingWindow(nums, k);
            System.out.println(Arrays.toString(result));
    
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.