LeetCode—剑指 Offer 59 - I、59 - II

剑指 Offer 59 - I. 滑动窗口的最大值、59 - II. 队列的最大值

题目描述：
[59 - I]
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
[59 - II]
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

考察重点：
第59 - I题使用优先队列(堆)实现窗口内元素排序，循环遍历模拟窗口滑动
第59 - II题使用一个单调队列进行辅助，保存队列元素大小关系。

第59 - I题

     class Num{
    
        int pos;
        int val;
        public Num(int pos, int val){
    
            this.pos = pos;
            this.val = val;
        }
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
    
        int[] res = new int[nums.length - k + 1];
        int recPos = 0;
        int left = 0, right = 0;
        int nLen = nums.length;
        if(nLen == 0){
    
            return new int[]{
    };
        }
        PriorityQueue<Num> pq = new PriorityQueue<>(new Comparator<Num>() {
    
            @Override
            public int compare(Num o1, Num o2) {
    
                if(o1.val > o2.val){
    
                    return -1;
                }else{
    
                    return 1;
                }
            }
        });

        while(right < nLen){
    
            Num num = new Num(right, nums[right]);
            pq.add(num);
            if(right - left >= k){
    
                for(Num p : pq){
    
                    if(p.pos == left){
    
                        pq.remove(p);
                        left ++;
                        break;
                    }
                }
            }
            if(right - left == k - 1)
                res[recPos++] = pq.peek().val;
            right ++;
        }
        return res;
    }

第59 - II题

class MaxQueue {
    
    public Deque<Integer> que;
    public Deque<Integer> help;

    public MaxQueue() {
    
        que = new ArrayDeque<>();
        help = new ArrayDeque<>();
    }

    public int max_value() {
    
        if(que.size() == 0)
            return -1;
        int val = help.getFirst();
        return val;
    }

    public void push_back(int value) {
    
        que.addLast(value);
        while(help.size() != 0 && value > help.getLast()){
      // help是一个单调队列，每个元素入队时，都会踢出前面比它小的对内元素，以此保障队列始终单调递减
            help.removeLast();
        }
        help.addLast(value);
    }

    public int pop_front() {
    
        if(que.size() == 0)
            return -1;
        int val = que.removeFirst();
        if(help.getFirst() == val) {
            // 先进一定先出，所以只需要比较出队元素是不是help队头元素即可
            help.removeFirst();
        }
        return val;
    }
}

/** * Your MaxQueue object will be instantiated and called as such: * MaxQueue obj = new MaxQueue(); * int param_1 = obj.max_value(); * obj.push_back(value); * int param_3 = obj.pop_front(); */