FireEmissary

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  14 随笔 :: 0 文章 :: 20 评论 :: 0 Trackbacks

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                  Max 
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note: 
You may assume k is always valid, 1 ≤ k ≤ input array's size.

Follow up:
Could you solve it in linear time?

Hint:

  1. How about using a data structure such as deque (double-ended queue)?
  2. The queue size need not be the same as the window’s size.
  3. Remove redundant elements and the queue should store only elements that need to be considered.


大意是用双向队列可以n的线性时间.网友的解法意思是前端移出了滑动窗口的元素要移除

然后新指向的元素和队列尾部元素比较,尾部小的元素也要移除.这样保持队列总是在滑动窗口里从大到小排好.

个人觉得当k比较大而输入元素基本随机时不可能是n复杂度.而应该是(k/2)*n左右


所以我的解法干脆用两个指针:最大值,第二大值来维护.实际运行还比双端队列快一点点.(92ms 击败90%)


vector<int> maxSlidingWindow(vector<int>& nums, int k) {
         
if(nums.size()<2)return nums;
        size_t n
=nums.size(), maxv=0,secondv=~0;
        vector
<int> out;
         
//secondv维持第二大的元素.如果maxv在窗口边界,secondv就是魔术~0代表不存在第二小元素.
         for(size_t i=1;i<k;++i)
            {
                
if(nums[i]>nums[maxv]){
                    maxv
=i;
                    secondv
=~0;
                }
else  if(secondv==~0||nums[i]>nums[secondv]){
                    secondv
=i;
                }
            }
         
out.push_back(nums[maxv]);
         
for(size_t i=k;i<n;++i)
         {
             
if(maxv<=i-k)
                 {
                     
                     
if(secondv==~0){
                         maxv
=i;
                     }
else{
                        maxv
=secondv;
                        secondv
=secondv+1;
                        
//maxv移出滑动窗口时,如果secondv存在,显然要更新它找出新的第二大元素.
                        for(size_t j=secondv+1;j<i;++j)
                            
if(nums[j]>nums[secondv])secondv=j;
                     }
                 }
             
if(nums[i]>nums[maxv]){
                 maxv
=i;
                  secondv
=~0;
             }
else  if(secondv==~0||nums[i]>nums[secondv]){
                    secondv
=i;
                }
                
out.push_back(nums[maxv]);
                
         }
        
return out;
    }



posted on 2016-07-24 14:54 FireEmissary 阅读(578) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理