239 Sliding Window Maximum (mono deque)

https://leetcode.com/problems/sliding-window-maximum/

mono deque，其实还是很像stack，push到last的时候都是从尾巴先pop掉不符合条件的元素，区别在于读答案是从头上读，并且每个循环需要先pop掉超出范围的元素。

deque中存的（除了头部之外）其实是当前范围内不会成为最大值，但是以后可能成为最大值的值的坐标（用坐标而不是值来方便判断是不是超出范围）。被从尾部pop掉的值都是因为有更新且更大的值所以他们直到出范围也不可能成为最大值了。

mono deque的特性，头部是当前范围内最大值，之后的值是未来范围内可能成为最大值的值，跟sliding window很搭配噢

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n-k+1];
        Deque<Integer> deque = new ArrayDeque<>();
        // 维护一个递减栈，每次更新后栈尾元素就是当前最大值，栈尾左边的元素不在栈中，
        // 要么是因为超出windows，要么是因为没有栈尾大不能保证递减
        // 而因为每次更新都会加进新的值，所以栈尾元素要么就是新值要么就是足够大没有被淘汰的旧值
        for (int i = 0; i < n; i++) {
            while (i >= k && !deque.isEmpty() && deque.peekLast() <= i-k) {
                deque.pollLast();
            }
            while (!deque.isEmpty() && nums[deque.peek()] < nums[i]) {
                //本质上就是说后来者有更大的，以后再怎么右移也不会轮到你们当最大值了
                deque.poll();
            }
            deque.push(i);
            if (i >= k - 1) {
                ans[i - k + 1] = nums[deque.peekLast()];
            }
        }
        return ans;
    }
}

...或者直接用treemap，慢一点但是能过

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int[] ans = new int[nums.length - k + 1];
        int idx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i < k) {
                map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
                if (i == k-1) {
                    ans[idx++] = map.lastKey();
                }
                continue;
            }
            int cnt = map.get(nums[i-k]);
            if (cnt == 1) {
                map.remove(nums[i-k]);
            } else {
                map.put(nums[i-k], cnt - 1);
            }
            map.put(nums[i], map.getOrDefault(nums[i],0)+1);
            ans[idx++] = map.lastKey();
        }
        return ans;
    }
}