问题:给定一个整数序列,定义f(i)为从元素i开始的连续k个元素的最小值,要求计算f(1),f(2)……f(n-k+1)
//一个序列,找从i开始,连续k个元素的最小值,要求输出所有的
//使用单调队列的思想
void q2(int arr[], int n, int k){
int q[4]; //队列
int result[n-4]; //结果
int result_index=0;
int front=-1,rear=0,num=0;//front用-1是为了方便判断 ,num指示队列中元素个数
int x=1;
//初始化q为单调并计算结果
q[0] = arr[0];
num++;
while(x<k){
if(q[rear] > arr[x]){
while(rear>=front){
if(q[rear] > arr[x]){
rear--;
num--;
}else{
break;
}
}
rear++;
q[rear] = arr[x];
num++;
}else{
rear++;
num++;
q[rear] = arr[x];
}
x++;
}
result[result_index] = q[front+1];
result_index++;
if(arr[0] == q[front+1]){
front++;
num--;
}
/*初始化结束*/
for(int i=k; i<n; i++){
if(q[rear] > arr[i]){
while(num!=0){
if(q[rear] > arr[i]){
rear = (rear+k-1)%k;
num--;
}else{
break;
}
}
rear = (rear+1)%k;
q[rear] = arr[i];
num++;
}else{
rear = (rear+1)%k;
q[rear] = arr[i];
num++;
}
result[result_index] = q[(front+1)%k];
if(arr[result_index] == q[(front+1)%k]){
front = (front+1)%k;
num--;
}
result_index++;
//输出
for(int i=0;i<4; i++){
printf("q:%d ",q[i]);
}
printf("front:%d,rear:%d,num:%d,result_index:%d, result:%d",front,rear,num,result_index-1, result[result_index-1] );
printf("\n");
}
//输出
for(int i=0;i<n-k+1; i++){
printf("%d\n",result[i]);
}
}
结果:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHL4VkeNlXR61UeFRUYxB3MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnL3EjMwADNxYTMwMzMwAjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)