122. 滑动窗口最大值（卡码网周赛第二十期（23年用友提前批笔试真题））

122. 滑动窗口最大值（卡码网周赛第二十期（23年用友提前批笔试真题））

题目描述

给定一个整数数组 nums 和一个整数 k，k 表示滑动窗口的大小。你需要找出每个滑动窗口中的最大值与最小值的差，并返回这些差的最大值。

输入

数组的长度为 n，1 <= n <= 10000，数组中的每个元素范围为[-10000,10000]，滑动窗口大小k的范围为[1,n]。

输出

例如，给定一个字符串 “nums = [1,3,-1,-3,5,3,6,7], k = 3”，表示一个数组和窗口大小 k。对于该数组中的每个窗口，计算最大值与最小值的差，并返回这些差值中的最大值。
在这个例子中，每个窗口的最大值与最小值的差分别为 [4, 6, 8, 8, 3, 4]，因此最终返回的结果是 8。

样例输入

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

样例输出

8

提示

题目输入是一个字符串，需要自己解析为数组和 k 值。

题解1（C++版本）

#include<bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10;
char s[N];
int n, k, a[N], mi[N], mx[N], q1[N], q2[N];

void getMax(){ //队头保存最大值 
	int h1 = 1, t1 = 0; //清空队列
	for(int i = 1; i <= n; i++){
		while(h1 <= t1 && a[q1[t1]] <= a[i]) t1--; //队尾出队 
		q1[++t1] = i; //队尾入队 
		if(q1[h1] < i - k + 1) h1++; //队头出队 
		if(i >= k) { // 使用最值 
			mx[i] = a[q1[h1]];
		}
	} 
}

void getMin(){ //队头保存最小值 
	int h2 = 1, t2 = 0; //清空队列
	for(int i = 1; i <= n; i++){
		while(h2 <= t2 && a[q2[t2]] >= a[i]) t2--; //队尾出队 
		q2[++t2] = i; //队尾入队 
		if(q2[h2] < i - k + 1) h2++; //队头出队 
		if(i >= k) { // 使用最值 
			mi[i] = a[q2[h2]];
		}
	} 
}

void read(){
    scanf("%[^\n]", s + 1); //读取一行字符串，直到读取到换行符为止
	int len = strlen(s + 1);
    int flag = 1, num = 0;
	int i = 1;
	
	for(; i <= len; i++){ // 读取数组中的元素
	    if(s[i] == '[') {
	        continue;
	    }else if(s[i] == ']'){ // 读取最后一个数组元素
	        a[++n] = num * flag;
	        num = 0;
	        flag = 1;
	        break;
	    }
	    if(s[i] == '-'){
	        flag = -1;
	    }else if(s[i] >= '0' && s[i] <= '9'){
	        num = num * 10 + s[i] - '0';
	    }else if(s[i] == ','){ 
	        a[++n] = num * flag;
	        num = 0;
	        flag = 1;
	    }
	}
	
	for(; i <= len; i++){ // 读取k
	    if(s[i] >= '0' && s[i] <= '9'){
	        k = k*10 + s[i] - '0';
	    }
	}
}
int main(){
	read(); // 读取数据
	getMin();getMax();
	int ans = 0;
	for(int i = k; i <= n; i++){
	    ans = max(ans, mx[i] - mi[i]);
	}
	printf("%d\n", ans);
	return 0;
}