剑指 Offer 59 - I. 滑动窗口的最大值

class Solution {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
    
        int n = nums.length;
        if(n == 0) return new int[0];
        int[] ans = new int[n - k + 1];
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for(int i = 0; i < k; i++){
    
            q.offer(new int[]{
    nums[i], i});
        }
        ans[0] = q.peek()[0];
        for(int i = k; i < n; i++){
    
            q.offer(new int[]{
    nums[i], i});
            while(q.peek()[1] <= i - k) q.poll();
            ans[i-k+1] = q.peek()[0];            
        }
        return ans;        
    }
}

class Solution {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
    
        int n = nums.length;
        if(n == 0) return new int[0];
        PriorityQueue<Integer> q = new PriorityQueue<>((i, j) -> nums[j] - nums[i]);
        int[] ans = new int[n - k + 1];
        for(int i = 0; i < k; i++){
    
            q.offer(i);
        }
        ans[0] = nums[q.peek()];
        for(int i = k; i < n; i++){
    
            q.offer(i);
            while(q.peek() <= i - k){
    
                q.poll();
            }
            ans[i-k+1] = nums[q.peek()];
        }
        return ans;
    }
} 

class Solution {
    
    public int[] maxSlidingWindow(int[] nums, int k) {
    
        int n = nums.length;
        if(n == 0) return new int[0];
        int[] res = new int[n - k + 1];
        Deque<Integer> q = new LinkedList<>();
        for(int i = 0; i < n; i++){
    
            // 单调队列
            while (!q.isEmpty() && nums[i] >= nums[q.peekLast()]) {
    
                q.pollLast();
            }
            q.add(i); // 索引
            int left = i - k + 1; // 当 left >= 0 时开始滑动窗口
            if (q.peek() < left) q.poll(); 
            if (left >= 0) res[left] = nums[q.peek()]; 
        }
        return res;
    }
}