剑指offer—用单调栈解决滑动窗口最大值问题

用双端队列来存储窗口数据,在存储的时候通过比较把最大值放在队首,每次将队首数据放入结果数组。
1.每次放入数据时,将该数据与队列末尾的元素数据相比较,小的出队,这样就保证了单调递减的队列;
2.判断队首元素是否出队。因为存储的是下标,所以通过比较下标即可知道是否出队。因为每次只移动1,所以只会有1个元素出队,用if即可不需要用while循环
3.如果元素下标已经达到窗口值,即可记录最大值。

 vectorint maxSlidingWindow(vectorint nums, int k) 
  {
		dequeint mark;
		vectorint res;
		int len=nums.size();
		if(len1)
			return res;
		for(int i=0;ilen;++i)
		{
		   while(!mark.empty ()nums[i]nums[mark.back ()])
			   mark.pop_back ();
		 if(!mark.empty ()mark.front ()i-k+1)
			   mark.pop_front ();
		   mark.push_back (i);
		   if(i=k-1)
			   res.push_back (nums[mark.front ()]);
		}
		return res;
  }
最新回复(0)
/jishuDXniPYsvXGEzpna3i8GZP1eTZ1Hh2fHf1LIEYQ_3D_3D4858758
8 简首页