题解 | #区间后缀极大位置计数#

题目描述

给定一个长度为 $n$ 的数列 $A$ 和一个整数 $m$ 。对于所有长度为 $m$ 的子区间（滑动窗口），你需要求出该子区间内“后缀最大值”位置的个数。

一个下标 $j$ 是数列 $b$ 的后缀最大值，当且仅当：对于所有的 $j < k \le |b|$ ，都有 $b_j \ge b_k$ ，其中 $|b|$ 表示 $b$ 的元素个数。

解题思路

本题要求对所有长度为 $m$ 的滑动窗口，计算其中后缀最大值的数量。一个朴素的解法是遍历每个窗口，再对窗口内的元素进行判断，总时间复杂度为 $\mathcal{O}(n \cdot m)$ ，会超时。

我们可以采用更高效的思路。首先分析一个元素 $A_k$ 在何时会成为一个后缀最大值。根据定义， $A_k$ 是某个窗口中的后缀最大值，当且仅当在该窗口内， $A_k$ 的右侧没有比它更严格大的元素。

这个性质让我们联想到 “下一个严格更大元素” (Next Strictly Greater Element, NSGE)。令 nsge[k] 为数组 $A$ 中 $A_k$ 右侧第一个值严格大于它的元素的索引。如果不存在，我们可以设 nsge[k] = n。

有了 nsge 数组，我们可以重新描述 $A_k$ 成为后缀最大值的条件： $A_k$ 是窗口 $[i, i+m-1]$ 中的一个后缀最大值，当且仅当：

$A_k$ 在窗口内，即 $i \le k < i+m$ 。
$A_k$ 的 NSGE 不在窗口内，即 nsge[k] >= i+m。

因此，问题转化为：对于每个窗口起始位置 $i$ （从 $0$ 到 $n-m$ ），计算满足 $i \le k < i+m$ 且 nsge[k] >= i+m 的 $k$ 的数量。

直接对每个窗口计算依然很慢。我们可以反过来考虑每个元素 $A_k$ 的贡献。对于固定的 $k$ ，它会对哪些窗口 $i$ 产生贡献（即成为这些窗口的后缀最大值）？

$A_k$ 对窗口 $i$ 产生贡献，需要满足：

i <= k (窗口包含 $k$ )
i >= k-m+1 (窗口包含 $k$ )
i <= nsge[k]-m (窗口不包含 $A_k$ 的 NSGE)

综合这三个条件，元素 $A_k$ 会对所有起始位置 $i$ 在区间 $[\max(0, k-m+1), \min(k, \text{nsge}[k]-m)]$ 内的窗口产生 $+1$ 的贡献。

现在问题转化为：我们有 $n$ 个“区间加一”的操作，需要在所有操作完成后，查询每个位置 $i$ （从 $0$ 到 $n-m$ ）的最终值。这是一个经典的差分问题。

算法流程：

预计算 NSGE: 使用单调栈，从右到左遍历数组 $A$ ，在 $\mathcal{O}(n)$ 时间内计算出所有元素的 nsge 数组。
构建差分数组: 创建一个大小为 $n+1$ 的差分数组 diff，初始化为 $0$ 。
区间更新: 遍历每个元素 $A_k$ （从 $k=0$ 到 $n-1$ ）：
a. 计算其贡献区间的左右端点 $L = \max(0, k-m+1)$ 和 $R = \min(k, \text{nsge}[k]-m)$ 。
b. 如果 $L \le R$ ，则在差分数组上执行更新：diff[L]++ 和 diff[R+1]--。
计算前缀和: 遍历差分数组 diff，计算其前缀和。前缀和数组的第 $i$ 个元素 ans[i] 就是第 $i$ 个窗口的后缀最大值数量。
输出结果: 输出 ans[0] 到 ans[n-m]。

整个算法的瓶颈在于预计算和差分更新，时间复杂度均为 $\mathcal{O}(n)$ ，因此总时间复杂度为 $\mathcal{O}(n)$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

int main() {
    using namespace std;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 1. 预计算 NSGE
    vector<int> nsge(n);
    stack<int> st;
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && a[st.top()] <= a[i]) {
            st.pop();
        }
        nsge[i] = st.empty() ? n : st.top();
        st.push(i);
    }

    // 2. 构建并更新差分数组
    vector<int> diff(n + 1, 0);
    for (int k = 0; k < n; ++k) {
        int left = max(0, k - m + 1);
        int right = min(k, nsge[k] - m);
        if (left <= right) {
            diff[left]++;
            if (right + 1 <= n) {
                diff[right + 1]--;
            }
        }
    }

    // 3. 计算前缀和并输出
    int current_count = 0;
    for (int i = 0; i <= n - m; ++i) {
        current_count += diff[i];
        cout << current_count << '\n';
    }

    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        // 1. 预计算 NSGE
        int[] nsge = new int[n];
        Stack<Integer> st = new Stack<>();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && a[st.peek()] <= a[i]) {
                st.pop();
            }
            nsge[i] = st.isEmpty() ? n : st.peek();
            st.push(i);
        }

        // 2. 构建并更新差分数组
        int[] diff = new int[n + 1];
        for (int k = 0; k < n; k++) {
            int left = Math.max(0, k - m + 1);
            int right = Math.min(k, nsge[k] - m);
            if (left <= right) {
                diff[left]++;
                if (right + 1 <= n) {
                    diff[right + 1]--;
                }
            }
        }

        // 3. 计算前缀和并输出
        int currentCount = 0;
        for (int i = 0; i <= n - m; i++) {
            currentCount += diff[i];
            out.println(currentCount);
        }
        out.flush();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))

    # 1. 预计算 NSGE
    nsge = [n] * n
    st = [] # 存储索引
    for i in range(n - 1, -1, -1):
        while st and a[st[-1]] <= a[i]:
            st.pop()
        if st:
            nsge[i] = st[-1]
        st.append(i)

    # 2. 构建并更新差分数组
    diff = [0] * (n + 1)
    for k in range(n):
        left = max(0, k - m + 1)
        right = min(k, nsge[k] - m)
        if left <= right:
            diff[left] += 1
            if right + 1 <= n:
                diff[right + 1] -= 1
    
    # 3. 计算前缀和并输出
    results = []
    current_count = 0
    for i in range(n - m + 1):
        current_count += diff[i]
        results.append(str(current_count))
    print('\n'.join(results))

if __name__ == "__main__":
    main()

算法及复杂度

算法: 单调栈、差分数组
时间复杂度: $\mathcal{O}(n)$ 。预计算 NSGE 数组需要 $\mathcal{O}(n)$ ，构建差分数组需要 $\mathcal{O}(n)$ ，计算前缀和并输出需要 $\mathcal{O}(n)$ 。
空间复杂度: $\mathcal{O}(n)$ ，用于存储 NSGE 数组和差分数组。