郑州专业的网站建设公司哪家好,高性能网站建设进阶指南下载,中企动力做的电梯网站,公司财务记账软件滑动窗口的最大值
题目链接 暴力解法
最容易想到的当然还是通过两层循环来暴力求解#xff1a;一层循环用来移动窗口#xff0c;一层循环用来在窗口内找到最大值。这种做法的时间复杂度为O(kN)#xff0c;会超出时间限制#xff0c;因此#xff0c;我们要找到更加高效的…滑动窗口的最大值
题目链接 暴力解法
最容易想到的当然还是通过两层循环来暴力求解一层循环用来移动窗口一层循环用来在窗口内找到最大值。这种做法的时间复杂度为O(kN)会超出时间限制因此我们要找到更加高效的方法。
单调队列
注这种解法建立在单调队列的基础之上而单调队列是双端队列的特殊形式如果对单调队列和双端队列还不太了解建议先看看详解单调队列
由于我们要求的是滑动窗口的最大值那我们不妨先做一个假设如果当前的滑动窗口中有两个下标i和j其中**i 在j的左侧i j并且i对应的元素不大于j对应的元素nums[i] nums[j]**。
那么我们就可以得到这样一个结论只要下标i所代表的元素nums[j]还在窗口中那么下标j所对应的元素nums[j]也一定在窗口中且**nums[i]一定不会是最大值**也就不会对答案造成影响我们也就可以将其直接删除了
也可以用一句话来概括 如果一个数据val要进入窗口那他窗口内所有比它小或等于它的的数都不会对答案造成影响 我们可以用一个队列来存储这些还没有被移除的元素的下标同时确保从队头到队尾这些下标是从小到大排列的保证数据的愿所有顺序而下标所代表的值是递减排列的这样队头元素就是滑动窗口的最大值了。
每当窗口向右滑动一个元素就会有一个新的元素入队。在这个元素入队之前由于我们要确保队列的单调递减性因此当队列不为空并且队尾元素小于或等于新的元素时就要通过循环删除这些不会对结果造成影响的元素最后再把这个元素的下标插入队列。
需要注意当窗口向右滑动时最大值下标会离开窗口永远不会在进入窗口因此在窗口滑动的过程中我们要不断比较队首元素的下标最大值下标和窗口最左侧的标下次移动时离开窗口的元素下标如果离开了窗口就要将队首元素出队。
例如对于上图的示例 实现代码
typedef struct DequeNode
{struct DequeNode* next;struct DequeNode* prev;int data;
}DQNode;typedef struct Deque
{DQNode* front;DQNode* tail;
}Deque;void DequeInit(Deque* pq) //双端队列初始化
{assert(pq);pq-front pq-tail NULL;
}bool DequeEmpty(Deque* pq) //双端队列判空
{assert(pq);return pq-front NULL;
}void DequePushTail(Deque* pq, int val) //队尾入队
{DQNode* newNode (DQNode*)malloc(sizeof(DQNode));newNode-data val;newNode-next NULL;newNode-prev NULL;if (DequeEmpty(pq)){pq-front pq-tail newNode;}else{pq-tail-next newNode;newNode-prev pq-tail;pq-tail newNode;}
}void DequePushFront(Deque* pq, int val) //队头入队
{DQNode* newNode (DQNode*)malloc(sizeof(DQNode));newNode-data val;newNode-next NULL;newNode-prev NULL;if (DequeEmpty(pq)){pq-front pq-tail newNode;}else{newNode-next pq-front;pq-front-prev newNode;pq-front newNode;}
}int DequePopFront(Deque* pq) //队头出队
{assert(pq);assert(!DequeEmpty(pq));DQNode* temp pq-front;int ret temp-data;pq-front pq-front-next;if (pq-front NULL)pq-tail NULL;elsepq-front-prev NULL;free(temp);return ret;
}int DequePopTail(Deque* pq) //队尾出队
{assert(pq);assert(!DequeEmpty(pq));DQNode* temp pq-tail;int ret temp-data;pq-tail pq-tail-prev;if (pq-tail NULL)pq-front NULL;elsepq-tail-next NULL;free(temp);return ret;
}int DequeTail(Deque* pq) //取队尾元素
{assert(pq);assert(!DequeEmpty(pq));return pq-tail-data;
}int DequeFront(Deque* pq) //取队头元素
{assert(pq);assert(!DequeEmpty(pq));return pq-front-data;
}void DequeDestroy(Deque* pq) //销毁双端队列
{while (!DequeEmpty(pq)){DQNode* temp pq-front;pq-front pq-front-next;free(temp);}free(pq);
}
//-------------------------------------双端队列基本功能实现-----------------------------------------------int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){*returnSize numsSize - k 1;int* ret (int*)malloc(sizeof(int) * (*returnSize));Deque* DQ_Max (Deque*)malloc(sizeof(Deque)); //用来记录最大值下标DequeInit(DQ_Max); //初始化//先将数组前k个入队列构建初始窗口for (int i0; ik; i){//队列不为空且队尾元素小于或等于新元素就将队尾元素删除//确保递减while (!DequeEmpty(DQ_Max) nums[DequeTail(DQ_Max)] nums[i]){DequePopTail(DQ_Max);}DequePushTail (DQ_Max, i); //将下标入队}ret[0] nums[DequeFront(DQ_Max)]; //初始窗口的最大值就是队头下下标所代表的元素//再将后面剩余的元素下标入队for (int ik; inumsSize; i){//删除不在窗口的下标while (!DequeEmpty(DQ_Max) DequeFront(DQ_Max) i - k)DequePopFront(DQ_Max);//队列不为空且队尾元素小于新元素就将队尾元素删除//确保非递增while (!DequeEmpty(DQ_Max) nums[DequeTail(DQ_Max)] nums[i]){DequePopTail(DQ_Max);}DequePushTail (DQ_Max, i);//窗口最大值就是队头下下标所代表的元素ret[i - k 1] nums[DequeFront(DQ_Max)];}//销毁队列释放内存DequeDestroy(DQ_Max);return ret;
}
