【RMQ 专题】关于 RMQ 的若干解法（内含彩蛋）

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3

输出：[3,3,5,5,6,7]

解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

输入：nums = [1], k = 1

输出：[1]

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

class Solution {
    class Node {
        int l, r, val;
        Node (int _l, int _r) {
            l = _l; r = _r; val = Integer.MIN_VALUE;
        }
    }
    Node[] tr = new Node[100010 * 4];
    void build(int u, int l, int r) {
        tr[u] = new Node(l, r);
        if (l == r) return ;
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
    void update(int u, int x, int v) {
        if (tr[u].l == x && tr[u].r == x) {
            tr[u].val = Math.max(tr[u].val, v);
            return ;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) update(u << 1, x, v);
        else update(u << 1 | 1, x, v);
        pushup(u);
    }
    int query(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r) return tr[u].val;
        int mid = tr[u].l + tr[u].r >> 1, ans = Integer.MIN_VALUE;
        if (l <= mid) ans = query(u << 1, l, r);
        if (r > mid) ans = Math.max(ans, query(u << 1 | 1, l, r));
        return ans;
    }
    void pushup(int u) {
        tr[u].val = Math.max(tr[u << 1].val, tr[u << 1 | 1].val);
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length, m = n - k + 1;
        int[] ans = new int[m];
        build(1, 1, n);
        for (int i = 0; i < n; i++) update(1, i + 1, nums[i]);
        for (int i = k; i <= n; i++) ans[i - k] = query(1, i - k + 1, i);
        return ans;
    }
}

class Solution {
    int n, m, len;
    int[] nums, region;
    int getIdx(int x) {
        return x / len;
    }
    void add(int x, int v) {
        region[getIdx(x)] = Math.max(region[getIdx(x)], v);
    }
    int query(int l, int r) {
        int ans = Integer.MIN_VALUE;
        if (getIdx(l) == getIdx(r)) {
            for (int i = l; i <= r; i++) ans = Math.max(ans, nums[i]);
        } else {
            int i = l, j = r;
            while (getIdx(i) == getIdx(l)) ans = Math.max(ans, nums[i++]);
            while (getIdx(j) == getIdx(r)) ans = Math.max(ans, nums[j--]);
            for (int k = getIdx(i); k <= getIdx(j); k++) ans = Math.max(ans, region[k]);
        }
        return ans;
    }
    public int[] maxSlidingWindow(int[] _nums, int k) {
        nums = _nums;
        n = nums.length; len = (int) Math.sqrt(k); m = n / len + 10;
        region = new int[m];
        Arrays.fill(region, Integer.MIN_VALUE);
        for (int i = 0; i < n; i++) add(i, nums[i]);
        int[] ans = new int[n - k + 1];
        for (int i = 0; i < n - k + 1; i++) ans[i] = query(i, i + k - 1);
        return ans;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> d = new ArrayDeque<>();
        int n = nums.length, m = n - k + 1;
        int[] ans = new int[m];
        for (int i = 0; i < n; i++) {
            while (!d.isEmpty() && nums[d.peekLast()] <= nums[i]) d.pollLast();
            d.addLast(i);
            if (i >= k - 1) {
                while (!d.isEmpty() && d.peekFirst() <= i - k) d.pollFirst();
                ans[i - k + 1] = nums[d.peekFirst()];
            }
        }
        return ans;
    }
}