剑指offer_滑动窗口的最大值

拼搏现实的明天。 2022-06-08 23:43 166阅读 0赞

/*
    给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
    例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，
    他们的最大值分别为{4,4,6,6,6,5}；
    针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： 
    {[2,3,4],2,6,2,5,1}， 
    {2,[3,4,2],6,2,5,1}， 
    {2,3,[4,2,6],2,5,1}， 
    {2,3,4,[2,6,2],5,1}， 
    {2,3,4,2,[6,2,5],1}， 
    {2,3,4,2,6,[2,5,1]}。
    
    //直接思路
    先求滑动窗口，再求最大值
    遍历数组，将每个元素开头的size个元素中求最大元素
    size过大可以，不影响，但size<=0不可以
    O(nk)，k为窗口大小
    
    剑指offer思路1：
    用队列做滑动窗口，每滑动一次，队列头部删除一个元素，尾部添加一个元素
    队列如果能满足在O(1)时间返回最大值，则整个只需要O(n)
    这样的队列可以用两个栈实现（面试题7），采用的栈是可以在O(1)时间返回最大值的栈（面试题21）
    
    剑指offer思路2：
    窗口是滑动形成的，最大值可能是以前窗口中的最大值，或者是新值。因此只要保存着以前窗口的最大值。 
    使用双端队列容器存储最大值在数组中的索引。队列头部是以前窗口中的最大值。
    
    当以前窗口的最大值被滑出窗口时，需要从队列头部删除。
    当新值大于队列中最大的数字时，删除队列中的所有数字，存储新值到队列。（新值索引靠后，老值已经没有可能成为新窗口的最大值）
    当新值不大于原有最大值时，当滑动新窗口时，仍有可能成为最大值，首先从队列尾依次删除比新值小的数字，然后存储到新值队列尾。
    */
    
    import java.util.ArrayList;
    import java.util.ArrayDeque;
    import java.util.Stack;
    
    class  MaxInWindows
    {
    	//直接思路，O(nk)
    	public static  ArrayList<Integer> maxInWindows(int [] num, int size)
        {
    		ArrayList<Integer> al=new ArrayList<Integer>();
            if (num==null||num.length<=0||size<=0||size>num.length)
            {
    			return al;
            }
    
    		for (int i=0; i<=num.length-size; i++)
    		{
    			int max=num[i];
    			for (int j=i+1; j<i+size;  j++)
    			{
    				if (num[j]>max)
    				{
    					max=num[j];
    				}
    			}
    			al.add(max);
    		}
    
    		return al;
        }
    
    	//剑指offer思路2
    	public static  ArrayList<Integer> maxInWindows2(int [] num, int size)
        {
    		ArrayList<Integer> al=new ArrayList<Integer>();
            if (num==null||num.length<=0||size==0)
            {
    			return al;
            }
    
    		/*
    		peekLast() 获取，但不移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。
    		pollLast() 获取并移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。
    		offerLast(E e) 将指定元素插入此双端队列的末尾。
    		peekFirst() 获取，但不移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。
    		pollFirst()  获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。
    		  */
    		ArrayDeque<Integer> dq = new ArrayDeque<>();
    		
    		//滑动窗口未满
    		for (int i=0; i<size; i++)
    		{
    			//当新值大于队列中最大的数字时，删除队列中的所有数字，存储新值到队列。
    			//当新值不大于原有最大值时，首先从队列尾依次删除比新值小的数字，然后存储到新值队列尾。
    			while (!dq.isEmpty()&&num[i]>=num[dq.peekLast()])
    			{
    				dq.pollLast();
    			}
    
    			dq.offerLast(i);//记录元素索引
    		}
    
    		//滑动窗口已满
    		for (int i=size; i<num.length; i++)
    		{
    			//第一个窗口的最大值
    			al.add(num[dq.peekFirst()]);
    
    			while (!dq.isEmpty()&&num[i]>=num[dq.peekLast()])
    			{
    				dq.pollLast();
    			}
    
    			if (!dq.isEmpty()&&i-dq.peekFirst()>=size)
    			{
    				dq.pollFirst();
    			}
    
    			dq.offerLast(i);
    		}
    
    		al.add(num[dq.peekFirst()]);
    		
    		return al;
        }
    
    	//剑指offer思路1：
    	public static  ArrayList<Integer> maxInWindows3(int [] num, int size)
        {
    		ArrayList<Integer> al=new ArrayList<Integer>();
            if (num==null||num.length<=0||size==0)
            {
    			return al;
            }
    
    		QueneWithTwoStacks quene=new QueneWithTwoStacks();
    		for (int i=0; i<size-1; i++)
    		{
    			quene.push(num[i]);
    		}
    
    		for (int i=size-1; i<num.length; i++)
    		{
    			quene.push(num[i]);
    			al.add(quene.max());
    			quene.pop();
    		}
    
    		return al;
    	}
    
    	public static void main(String[] args) 
    	{
    		int[] num={2,3,4,2,6,2,5,1};
    		ArrayList<Integer> al=maxInWindows3(num,3);
    		for (int i:al )
    		{
    			System.out.println(i);
    		}
    	}
    }
    
    class QueneWithTwoStacks 
    {
    	public  StackWithMax  stack1 = new StackWithMax();
        public  StackWithMax  stack2 = new StackWithMax();
        
        public void push(int node) 
    	{
            stack1.push(node);
        }
        
    	public int pop() 
    	{
    		if (stack2.empty())//stack2为空时将stack1中元素移到stack2，若stack2不为空则直接弹出stack2中的栈顶
    		{
    			//将stack1中元素移到stack2，元素顺序将随之反转
    			while (!stack1.empty())
    			{
    				stack2.push(stack1.pop());
    			}
    		}
    		
    		return stack2.pop();
        }
    
    	public int max()
    	{
    		return stack2.max()>stack1.max()? stack2.max():stack1.max();
    	}
    }
    
    class StackWithMax
    {
    	public  Stack<Integer> sData=new Stack<Integer>();//数据栈
    	public  Stack<Integer> sMax=new Stack<Integer>();//辅助栈
    
    	public void push(int node) 
    	{
    		sData.push(node);
    
            if (sMax.empty()||node>top())压栈元素node大于最大元素时，更新最大元素，将node压入辅助栈sMax
            {
    			sMax.push(node);
            }
    		//压栈元素node小于最大元素时,辅助栈不进行任何操作
        }
        
        public int pop() 
    	{
            int topData=sData.pop();
    		if (topData==top())
    		{
    			sMax.pop();//与压栈对应，出栈元素等于最大元素时，辅助栈更新，弹出栈顶
    		}
    		//出栈元素不等于最大元素时，辅助栈不进行任何操作
            return topData;
        }
        
        public int top() 
    	{
    		int t=sMax.pop();
    		sMax.push(t);
    		return t;
        }
        
        public int max() 
    	{
    		return top();
        }
    
    	public boolean empty()
    	{
    		return sData.empty();
    	}
    
    }