首页 > 试题广场 >

Stack (30)

[编程题]Stack (30)

热度指数：5449 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

Stack is one of the most fundamental data structures, which is based on the principle of Last In First Out (LIFO). The basic operations include Push (inserting an element onto the top position) and Pop (deleting the top element). Now you are supposed to implement a stack with an extra operation: PeekMedian -- return the median value of all the elements in the stack. With N elements, the median value is defined to be the (N/2)-th smallest element if N is even, or ((N+1)/2)-th if N is odd.

输入描述:

Each input file contains one test case.  For each case, the first line contains a positive integer N (<= 10⁵).  Then N lines follow, each contains a command in one of the following 3 formats:
Push key
Pop
PeekMedian
where key is a positive integer no more than 10⁵.

输出描述:

For each Push command, insert key into the stack and output nothing.  For each Pop or PeekMedian command, print in a line the corresponding returned value.  If the command is invalid, print "Invalid" instead.

示例1

输入

17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop

输出

Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid

算法知识视频讲解

1.树状数组+二分查找

树状数组(Binary Indexed Tree(BIT))是一种能高效查找前缀和的数据结构，具体实现原理见鄙人还没写好的拙作《树状数组的复习》。使用树状数组是为了能进行二分查找，原先遍历Count数组，最多的时候能遍历10^5次，运用二分查找可以将查找次数优化为lg(10^5)/lg(2) < 15

下面是代码

<span style="font-family:Comic Sans MS;font-size:14px;">

# include <cstdio>
# include <stack>
using namespace std;
class BIT
{
private:
    int *Elem;
    int Size;
    int lowbit(int n)
    {
	    return n&(-n);
	}
public:
    BIT(int size):Size(size+1)  /*想想看还是+1好了，要不申请了100的空间只能用到99感觉太奇怪了*/
    { 
	    Elem = new int[Size];
	    for (int i=0;i<Size;i++)/*还没试过用memset初始化，下次试试*/
	        Elem[i] = 0;
	}
	int GetSum(int right)/*[0,right]*/
	{
	    int sum = 0;
	    while (right)
	    {
		    sum += Elem[right];
		    right -= lowbit(right);
		}
		return sum;
	}
	int GetSum(int left,int right)/*[left,right]*/
	{
	    return GetSum(left-1) - GetSum(right);
	}
    void Add(int value,int index)
    {
	    while (index < Size)
		{
		    Elem[index] += value;
		    index += lowbit(index);
		} 
	}
    ~BIT()
    {
      delete[] Elem;
	}
};
BIT bit(100000);
int getmid(int size)
{
	int index = (size+1)/2;
	int left = 1,right = 100000,mid;
    while(left<right)
	{
        mid = (left+right)/2;
        if(bit.GetSum(mid)<index)
            left = mid+1;
        else
            right = mid;
    }
    return left;
}
int main()
{
  int n,tmp;
  scanf("%d",&n);
  stack<int> s;
  char str[10];
  while (n--)
  {
      scanf("%s",str);
      switch(str[1])
      {
	      case 'e':
		      {
			  if (s.empty()) 
			      printf("Invalid\n");
			  else 
			      printf("%d\n",getmid(s.size()));
			  break;
			  }
	      case 'o':
		      {
    	      if (s.empty())
    	          printf("Invalid\n");
	          else 
                  {
          	      tmp = s.top();s.pop();
          	      printf("%d\n",tmp);
                  bit.Add(-1,tmp);
				  }
			  break;
			  }
	      case 'u':
		  	  {
	              scanf("%d",&tmp);s.push(tmp);
                  bit.Add(1,tmp);
			  }
			  break;
	  }
  }
  return 0;
}</span>

2.分桶法（分治，分层HASH，平方分割）本人快乐

的原创

分桶法的基本思路是分治，在一开始的暴力解法中，我们可以认为Count数组是一个大的桶，这个大的桶里有 5*10^5个小桶，每个小桶能装一个数，在分桶法中，我们建立多个大桶，每个桶中又有小桶，比如，我们建立多个 500个大桶，每个桶的容量是100，同时记录每个大桶中存放的数据的个数，在查找的时候我们可以通过每个大桶中元素的快速定位到放置中位数的那个小桶。当然你可以认为这是一种HASH，hash(key) = key/10。

设每个大桶中含有k个小桶，共有m个大桶，m*k = n为定值。则一开始我们需要遍历大小为m的大桶数组，后来要遍历大小为k单个大桶，时间复杂度为O（max(k,m))在n*k为定值的情况下，易知m = k = （m*k）^(1/2)的时候效率最高为n^(1/2)。

本题中为了方便，采用分层hash的策略，将值为key的元素放入bucke[k/100][k%100]中。

# include <cstdio>
# include <stack>
using namespace std;

const int _size = 100000;
const int capi  = 500;
int bucket[_size/capi][capi];
int count[_size/capi];
int getmid(int size)
{
	int ind = (size+1)/2,cnt=0,i,j;
    for (i=0;i<_size/capi;i++)
        {
		if (cnt + count[i]>=ind)
            break;
		cnt += count[i];
		}
	for (j=0;j<capi;j++)
	    {
		cnt += bucket[i][j];
	    if (cnt>=ind)
	        return j+i*capi;
		}
    
}
char str[10];
int main()
{
  int n,tmp;
  scanf("%d",&n);
  stack<int> s;
  while (n--)
  {
      scanf("%s",str);
      switch(str[1])
      {
	      case 'e':
		      {
			  if (s.empty()) 
			      printf("Invalid\n");
			  else 
			      printf("%d\n",getmid(s.size())+1);

			  break;
			  }
	      case 'o':
		      {
    	      if (s.empty())
    	          printf("Invalid\n");
	          else 
                  {
          	      tmp = s.top();s.pop();
          	      printf("%d\n",tmp);
          	      tmp--;
			      bucket[tmp/capi][tmp%capi]--;
			      count[tmp/capi]--;
				  }
			  break;
			  }
	      case 'u':
		  	  {
	              scanf("%d",&tmp);s.push(tmp);
                  tmp--;
                  bucket[tmp/capi][tmp%capi]++;
			      count[tmp/capi]++;
			  }
			  break;
	  }
  }
  return 0;
}

最后我想说的就是，

1. 这个方法和树状数组 + 二分的方法并无矛盾，你同样可以用树状数组优化大桶元素的前缀和。

2. 还有就是如果你乐意你完全可以多分几个层玩 , 比如 key 放在 bucket[...][...][...], 分层分多了以后，你会发现这个桶变成了一棵树，如果你分层的依据是二分法，你还会发现，你分出了一棵线段树。

3. 如果数据范围增大，你可以修改 hash 使其映射到更小的空间，同时将每个大桶改为 vector<int> 数组，查询是对每个 vector<int> 中的元素排序，个人感觉不会很慢

3.线段树（分治）有种杀鸡用牛刀的感觉

线段树是个霸气的数据结构，基本上包含了分桶法和树状数组的全部功能。线段树的基础思想是分治，但是时间

复杂度上比分桶法更加高效，能将时间优化到O（lgn）然而在PAT的小数据之下，普通的线段树因为常数上的差距花

费的时间更长。具体的树的创建我就不说了，这里采用一点zkw线段树的思想，直接找到树的叶子自底向上走到树根，每个节点维护一个Cnt记录经过这里的路径的个数，查找中位数的时候根据每个节点的Cnt进入合适的子树进行查找。

# include <cstdio>
# include <stack>
using namespace std;

typedef int Node;
class zkw_segtree
{
private:
    Node *T;
	int size;
public:
    zkw_segtree(int range)
	{
	    for (size = 1;size < range+2;size<<=1);
	    T = new Node[2*size];
	    for (int i=1;i<size+size;i++)
		    T[i] = 0;    
	} 
	void Add(int value,int index)
	{
		index += size;
	    for (T[index]+=value,index>>=1;index>0;index>>=1)
            T[index] = T[index<<1]  + T[(index<<1) + 1];
	}
	int Query(int s,int t)
	{
	    int ret = 0;
	    for (s+=size-1,t+=size-1;s^t^1;s>>=1,t>>=1)
	        {
			  if (~s^1) ret += T[s^1];
			  if (t^1)  ret += T[t^1]; 
			}
	    return ret;
	}
	int Find_Kth(int k,int root = 1)
	{
	    while (root<<1 < size<<1)
		{
		  if (T[root<<1]>=k)  root = root<<1;
          else 
		    {
			  k -= T[root<<1];
			  root = (root<<1) + 1;
		    }
		}		    
	    return root - size;
	}
	~zkw_segtree()
	{
	    delete[] T;
	}
};
zkw_segtree segtree(100000);
int main()
{
  int n,tmp;
  scanf("%d",&n);
  stack<int> s;
  char str[10];
  while (n--)
  {
      scanf("%s",str);
      switch(str[1])
      {
	      case 'e':
		      {
			  if (s.empty()) 
			      printf("Invalid\n");
			  else 
			      printf("%d\n",segtree.Find_Kth((s.size()+1)/2));
			  break;
			  }
	      case 'o':
		      {
    	      if (s.empty())
    	          printf("Invalid\n");
	          else 
                  {
          	      tmp = s.top();s.pop();
          	      printf("%d\n",tmp);
                  segtree.Add(-1,tmp);
				  }
			  break;
			  }
	      case 'u':
		  	  {
	              scanf("%d",&tmp);s.push(tmp);
                  segtree.Add(1,tmp);
			  }
			  break;
	  }
  }
  return 0;
}

测试完发现是最快的，不愧是zkw大神的杰作

3.Prioriry Queue On Multiset(红黑树是支持插入与删除的堆)真正的牛刀

讲了那么多终于讲到最终的解法了，前三种方法归根结底是利用了输入数据范围有限这一条件，要想完美解决这一问题，我们不得不借助插入查找删除效率都为O（lgn）的高级搜索树。

有一种利用堆查找第K个元素的算法，维持一个大顶堆，一个小顶堆，将K个元素压入小顶堆，其余压入大顶堆，随后如果大顶堆的堆顶元素大于小顶堆的堆顶元素，就将将两个堆得元素弹出并压入另一个堆中，直到大顶堆的堆顶元素小于小顶堆的堆顶元素。这样小顶堆的堆顶元素就是第K个元素。

然而对于这道题，这种算法并没有什么用处，这道题要求随时删除某一个元素，然而堆并不具备这种功能（ ~~废话，能随意删除某个元素还叫堆吗~~ ）。。

犹记得当初学数据结构的时候，是先教的高级搜索树，后教的优先队列。老师在教优先队列的时候，为了引出堆，说，其实想要实现优先队列，用高级搜索树是完全可以的，但高级搜索树实在是太强大了，实现也比较复杂，我们需要一种更简单高效的数据结构去实现优先队列。

于是传说中的堆诞生了，因为堆在结构上的特点，我们也无法做到随意删除其中的某个元素。

然而此时我们需要一个能删除任意元素的优先队列，OK，~~是时候启动最终形态了，优先级队列超进化，红黑优先级队列~~。以上文字过于中二，请谨慎阅读。

从时间复杂度上分析，插入查找和删除都是O（lgn）这里的n是指总元素的个数。

然后，估计大家都知道要怎么做了，下面是代码，为了简单起见，并没有扩展出寻找第K个数的功能，而是直接寻找中位数。

# include <cstdio>
# include <stack>
# include <set>
using namespace std;

const int debug = 1;
typedef int T;
class Find_Median
{
private:
    multiset<T,greater<T> > maxheap;
	multiset<T,less<T> > minheap;
public: 
    void Push(T data)
	{
	    if (maxheap.size() < minheap.size()) 
            maxheap.insert(data);
        else 
		    minheap.insert(data);
	}
	bool Erase(T data)
	{
		multiset<T>::iterator it;
        if ((it=maxheap.find(data))!=maxheap.end())  
		    maxheap.erase(it);
		else if ((it=minheap.find(data))!=minheap.end()) 
	 	    minheap.erase(it);
        else 
            return false;
        return true;
	}
	T Query()
	{
		while (maxheap.size() < minheap.size())  
        {
            maxheap.insert(*minheap.begin());
            minheap.erase(minheap.begin());
		}
		while (minheap.size() < maxheap.si敏感词heap.insert(*maxheap.begin());
			maxheap.erase(maxheap.begin());   
		}
		
		if (maxheap.size()==0) return *minheap.begin();
		if (minheap.size()==0) return *maxheap.begin();
		
        multiset<T>::iterator maxtop = maxheap.begin();     	
	    multiset<T>::iterator mintop = minheap.begin(); 
	    while (*maxtop > *mintop)
	    {
            maxheap.insert(*mintop);
			minheap.insert(*maxtop);
            maxheap.erase(maxtop); 					
		    minheap.erase(mintop);
		    maxtop = maxheap.begin(); 
		    mintop = minheap.begin(); 
		}
        return *(maxheap.size() >= minheap.size()?maxtop:mintop);
	}   
};
Find_Median FM;
int main()
{
  int n,tmp;
  scanf("%d",&n);
  stack<int> s;
  char str[10];
  while (n--)
  {
      scanf("%s",str);
      switch(str[1])
      {
	      case 'e':
		      {
			  if (s.empty())  printf("Invalid\n");
			  else 
                  printf("%d\n",FM.Query());
			  break;
			  }
	      case 'o':
		      {
    	      if (s.empty())  printf("Invalid\n");
	          else 
                  {
          	      tmp = s.top();s.pop();
          	      printf("%d\n",tmp);
                  FM.Erase(tmp);
				  }
			  break;
			  }
	      case 'u':
		  	  {
	              scanf("%d",&tmp);s.push(tmp);
                  FM.Push(tmp);
			  }
			  break;
	  }
  }
  return 0;
}

看起来是最慢的，一半怪stl太慢，一半怪我的实现太渣

编辑于 2015-08-18 21:40:33 回复(6)

提交观点

问题信息

栈高级结构

难度：

0条回答 16收藏 15676浏览

通过挑战的用户

顾日天

2023-03-15 18:09:22
牛客84209...

2023-03-11 13:42:59
Jasper_H

2023-03-04 22:08:52
不想上班啤酒肚是单身

2023-02-24 16:22:16
Eddddddy

2023-02-24 14:39:23