数据库碎片是影响数据库性能的一个大因素，应及时发现并整理碎片。一. 碎片是如何产生的 当创建一个数据库实例时，会分成称为表空间（tablespace）的多个逻辑段（segment），如系统（system）表空间,临时（temporary）表空间等。一个表空间可以包含多个数据范 题目：给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。
例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，它们的最大值分别为{4,4,6,6,6,5}。
   滑动窗口这个概念在写过网络编程的人都应该是不陌生，主要是用来进行流控的。利用接收方剩下的缓冲数据区的大小来控制发送端的发送速度，避免发送端发送过快，导致网络拥塞及其他故障问题。
方案一：蛮力法，顺序分块扫描。例如在上例中，我们进行不断的分组和查找，3个一组，这样最终会找出其最大值。但是其时间复杂度为O(NK)。N为滑动窗口的数量，K为滑动窗口的大小。
方案二：栈实现。滑动窗口我们知道是先进先出的数据处理顺序，很明显是一个队列。在[21]中我们知道我们可以用栈来实现一个O(1)时间复杂度来得到最大值，在[6]中我们也讲到过用两个栈来实现一个队列，这样我们可以用两个栈来实现队列，同时也可以用O(1)的时间来得到栈中的最大值。所以总的时间复杂度就降低到了O(N).

方案三：双端队列实现。由于方案二中实现的步骤比较复杂，所以我们换了一种思路，在取得最大值的过程中，我们并不把每个数值都存入队列，而只是把有可能成为最大值的数据存入到两端开口的队列(deque)中，上面的输入为例，其求解过程如下：

具体实现代码如下：

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int arr[8]={2,3,4,2,6,2,5,1};
vector<int> array(arr,arr+8);
deque<int> index;
vector<int> maxWindows;
vector<int> GetmaxInWindows(const vector<int> &data,int size)
{
	if(data.size()>=size && size>=1)
	{
		for(int i=0;i<size;i++) //前三个入队并找出最大的值；
		{
			while(!index.empty() && data[i]>=data[index.back()])
				index.pop_back();
			index.push_back(i);
		}


		for(int i=size;i<data.size();i++)
		{
			maxWindows.push_back(data[index.front()]);//将最大值如队列；
			while(!index.empty() && data[i]>=data[index.back()])
				index.pop_back();
			if(!index.empty() && index.front()<=(int)(i-size))
				index.pop_front();//最大的值已经从窗口滑出了；
			index.push_back(i);
		}
		maxWindows.push_back(data[index.front()]);//最后一个数一定是最大的；
	}
	return maxWindows;
}

int main()
{
	vector<int> result;
	result=GetmaxInWindows(array,3);
	vector<int>::iterator it;
	cout<<"滑动窗口的最大值为：";
	for(it=result.begin();it!=result.end();it++)
		cout<<*it<<" ";
	cout<<endl;
	system("pause");
	return 0;
}

运行结果：

顶

0

踩

0