2158 前缀极差
小于 1 分钟
2158 前缀极差
【算法】 前缀最值
【C++】 一维数组、前缀最大值、前缀最小值
【难度】 入门
一、题目简述
有 个数(), 次询问,每次询问前 个数的极差(最大值 - 最小值)。
二、解题思路
维护两个前缀数组:
preMax[i]:前 个数的最大值 =max(preMax[i-1], a[i])preMin[i]:前 个数的最小值 =min(preMin[i-1], a[i])
每次询问前 个数的极差 = preMax[x] - preMin[x]。
手动模拟:[3, 2, 4, 5, 1]
- x=1: max=3, min=3, 极差=0
- x=3: max=4, min=2, 极差=2
- x=5: max=5, min=1, 极差=4
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], preMax[N], preMin[N];
int main() {
int n, q;
scanf("%d%d", &n, &q);
preMin[0] = 2e9; // 初始化为极大值
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
preMax[i] = max(preMax[i - 1], a[i]);
preMin[i] = min(preMin[i - 1], a[i]);
}
while (q--) {
int x;
scanf("%d", &x);
printf("%d ", preMax[x] - preMin[x]);
}
printf("\n");
return 0;
}四、复杂度分析
- 时间:
- 空间:
