栈和队列——生成窗口最大值数组

太过爱你忘了你带给我的痛 2022-06-08 00:36 131阅读 0赞

【题目】  
　　有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。  
　　例如，数组为\{4,3,5,4,3,3,6,7\}，窗口大小为3时：  
　　\{4 3 5\} 4 3 3 6 7  
　　4 \{3 5 4\} 3 3 6 7  
　　4 3 \{5 4 3\} 3 6 7  
　　4 3 5 \{4 3 3\} 6 7  
　　4 3 5 4 \{3 3 6\} 7  
　　4 3 5 4 3 \{3 6 7\}  
　　如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。  
　　请实现一个函数。  
　　·输入：整型数组arr，窗口大小为w  
　　·输出：一个长度为n-w+1的数组res，res\[i\]表示每一种窗口状态下的最大值  
　　以本题为例，结果应该返回\{5,5,5,4,6,7\}

【解答】  
　　如果数组长度为N，窗口大小为w，如果做出时间复杂度O(N x W)的解法是不能让面试官满意的。本题要求想出时间复杂度O(N)的实现  
　　具体解法不难，看代码自己走吧

【代码实现】

import java.util.LinkedList;
    class Demo{
        public static void main(String[] args){
            int[] arr = {
       4,3,5,4,3,3,6,7};
            //传arr数组，和窗口长度3
            int[] result = getMaxWindow(arr,3);
            for(int i=0;i<result.length;i++){
                System.out.print(result[i]+" ");
            }
            System.out.println();
        }
    
        public static int[] getMaxWindow(int[] arr,int w){
            //如果数组为空或者窗口长度小于1或者数组长度小于窗口长度，返回
            if(arr == null || w<1 || arr.length < w){
                return null;
            }
            LinkedList<Integer> qmax = new LinkedList<Integer>();
            int[] res = new int[arr.length-w+1];
            int index = 0;
            for(int i = 0;i<arr.length;i++){
                while(!qmax.isEmpty() && arr[qmax.peekLast()]<=arr[i]){
                    qmax.pollLast();
                }
                qmax.addLast(i);
                if(qmax.peekFirst() == i-w){
                    qmax.pollFirst();
                }
                if( i >= w-1){
                    res[index++] = arr[qmax.peekFirst()];
                }
            }
            return res;
        }
    }