剑指Offer-滑动窗口的最大值

package StackAndQueue;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;
/**
 * 滑动窗口的最大值
 * 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。
 */
public class Solution52 {
    public static void main(String[] args) {
        Solution52 solution52 = new Solution52();
        int[] num = {2, 3, 4, 2, 6, 2, 5, 1};
        int size = 3;
        ArrayList list = solution52.maxInWindows(num, size);
        System.out.println(list);
    }
    /**
     * 最大堆方法
     * 构建一个窗口size大小的最大堆，每次从堆中取出窗口的最大值，随着窗口往右滑动，需要将堆中不属于窗口的堆顶元素删除。
     *
     * [@param num
     * @param size
     * @return](/profile/547241) */
    public ArrayList maxInWindows_2(int[] num, int size) {
        ArrayList res = new ArrayList();
        if (size > num.length || size < 1) return res;
        // 构建最大堆，即堆顶元素是堆的最大值。
        PriorityQueue heap = new PriorityQueue((o1, o2) -> o2 - o1);
        for (int i = 0; i < size; i++) heap.add(num[i]);
        res.add(heap.peek());
        for (int i = 1; i + size - 1 < num.length; i++) {
            heap.remove(num[i - 1]);
            heap.add(num[i + size - 1]);
            res.add(heap.peek());
        }
        return res;
    }
    /**
     * 双队列方法
     * 滑动窗口的最大值总是保存在队列首部，队列里面的数据总是从大到小排列。
     *
     * [@param num
     * @param size
     * @return](/profile/547241) */
    public ArrayList maxInWindows(int[] num, int size) {
        ArrayList res = new ArrayList();
        if (num == null || num.length == 0 || size == 0 || size > num.length) {
            return res;
        }
        Deque deque = new LinkedList();
        for (int i = 0; i < num.length; i++) {
            if (!deque.isEmpty()) {
                // 如果队列头元素不在滑动窗口中了，就删除头元素
                if (i >= deque.peek() + size) {
                    deque.pop();
                }
                // 如果当前数字大于队列尾，则删除队列尾，直到当前数字小于等于队列尾，或者队列空
                while (!deque.isEmpty() && num[i] >= num[deque.getLast()]) {
                    deque.removeLast();
                }
            }
            deque.offer(i); // 入队列
            // 滑动窗口经过一个滑动窗口的大小，就获取当前的最大值，也就是队列的头元素
            if (i + 1 >= size) {
                res.add(num[deque.peek()]);
            }
        }
        return res;
    }
}

class Solution {
public:
    //只考虑两端增删变化的影响
    int MaxinW(const vector& num, int low, int high)
    {
        int MaxVal = INT_MIN;
        for (int j = low; j <= high; j++)
            MaxVal = max(num[j], MaxVal);
        return MaxVal;
    }
    vector maxInWindows(const vector& num, unsigned int size)
    {
        vectorres;
        int len=num.size();
        if (len len)return res;
        int MaxVal = MaxinW(num, 0, size - 1); res.push_back(MaxVal);
        for (int low = 1, high = size; high < len; low++,high++)
        {
            if (num[high] >= MaxVal)
                MaxVal = num[high];
            if (num[low - 1] == MaxVal)
                MaxVal = MaxinW(num, low, high);
            res.push_back(MaxVal);
        }
        return res;
    }
};

2.参考牛友

class Solution {
public:
    //双端队列
    //时间复杂度o（n），空间复杂度为o（n）
    //deque s中存储的是num的下标
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int>res;
        deque<int>s;
        int len=num.size();
        if (len <= 0||size<=0||size>len)return res;         
        for (int i = 0;i < len; i++)
        {
            while (!s.empty() && num[s.back()] <= num[i])//当前值比队列从后往前的大，成为下一个待选值
                s.pop_back();
            while (!s.empty()&&i - s.front() + 1>size)//最大值已不在窗口中
                s.pop_front();
            s.push_back(i);

            if (i + 1 >= size)//当滑动窗口首地址i大于等于size时才开始写入窗口最大值
             res.push_back(num[s.front()]);
        }
        return res;
    }

};

python O（n） solution

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, nums, k):
        # write code here
        if not k or k>len(nums):return []

        cur_max = max(nums[:k])
        max_nums = [cur_max]
        for i in range(0, len(nums) - k):
            if nums[i] == cur_max:
                cur_max = max(nums[i + 1:i + k + 1])
            elif nums[i + k] > cur_max:
                cur_max = nums[i + k]
            max_nums.append(cur_max)
        return max_nums

双端队列，两端删除添加可用数组模拟。
push/pop操作最后
unshift/shift操作最前

function maxInWindows(num, size)
{
  // 双端队列（两端都可以实现插入和删除）
  // 队列首位永远是最大值
  // 每次进来一个数，依次和前面的数比较，如果进来的数大，则前面的数直接弹出（在后面不可能最大）
  // 如果进来的数小，则比较下标，下标不存在的将其删除

  // 数组实现双端队列，arr存的是下标，arr[0]存最大值下标
  var arr = [];
  // 结果数组
  var res = [];

  if (size === 0) {
    return res;
  }

  for (var i = 0; i < num.length; i++) {
    // 从第一个开始循环（可以理解成滑动窗口右侧从第一个移动到最后一个）
    // 进来一个数，依次从最后一个数开始比较
    while (arr.length > 0 && num[i] > num[arr[arr.length-1]]) {
      // 如果进来的数比最后一个大，则将最后一个踢出去，pop
      arr.pop();
    }
    arr.push(i);

    // 再判断前面的数是否超了，由于每次进来的数如果更大，则将前面的踢出去，导致arr[0]的下标永远在最前面
    if (i - arr[0] + 1 > size) {
      arr.shift();
    }
    if (i >= size - 1) {
      res.push(num[arr[0]]);
    }
  }
  return res;
}

var res = maxInWindows([2,3,4,2,6,2,5,1], 3);
console.log(res);

function maxInWindows(num, size)
{
    // write code here
    if(!num){
        return null;
    }
    var len = num.length;
    var arr = [];
    if(size > len || size <= 0){
        return arr;
    }
    if(size == 1){
        return num;
    }
    if(size == len){
        //注意这里用Math.max()的时候，如果直接传的是数组名，要在前面加...符号，不然不成功
        arr.push(Math.max(...num));
        return arr;
    }
    for(var i = 0;i < len - size + 1;i++){
        var num1 = [];
        num1 = num.slice(i,i+size);
        arr.push(Math.max(...num1));
    }
    return arr;
}
if好像写的有点多~

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        #双端队列维护从大到小元素的索引
        #步骤
        #每遇到一个元素，从后往前将队列中小于该元素的索引全部弹出
        #（因为在滑动窗口长度内，小于该元素的值不可能成为最大值，1是该元素在他们后面，2是该元素值比他们大）
        if size>len(num) or size<1:
            return []
        from collections import deque
        queue = deque()
        res = [] 
        for index,val in enumerate(num):
            #队列为空时加入第一个元素
            if index==0:
                queue.append(index)
            else:
                #判断队首是否滑出了窗口
                if index-queue[0]==size:
                    queue.popleft()
                #为当前元素在队列中找到相应位置，其后所有元素弹出
                while queue and num[index]>=num[queue[-1]]:
                    queue.pop()
                queue.append(index)
                print(queue)
            #当滑动窗口大小==size时，可以开始记录最大值
            if index>=size-1:
                res.append(num[queue[0]])
        return res 

/*
表达不清楚的地方，请各位批评指正！
这道题可以用双向队列解决(就是头尾都可以push，pop的队列)
时间复杂度 O(N)
方法如下几点:
    1.当我们遇到新数时候，将新的数和双向队列的末尾比较，
       若果末尾比新数小，则把末尾pop_back，
       直到末尾比新数大或者队列为空才停止；
     2.这样就保证队列元素是从头到尾降序的，
         由于队列里只有窗口内的数，所以它们其实是窗口内
         第一大，第二大…的数。
     3.保持队列里只有窗口大小的数的方法是，
         右边进一个，左边出一个。
     4.由于队列加新数时，已经删除了部分没用的数，
        所以队列头的数并不一定是窗口最左的数，
        这里有个小技巧，就是队列中存原数组的下标，
        这样既可以得到这个数，也可以判断是否是窗口
        左边的数了。
*/
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> ret;
        if(num.empty() || size == 0)
            return ret;
        deque<int> deq;
        for(unsigned int i = 0;i < num.size(); ++i){
            //每当新数进来时，如果队列头部的下标是窗口最左边的下标，则删除队列头
            if(!deq.empty() && deq.front() < i - size)
                deq.pop_front();
            //队列中加入新数
            deq.push_back(i);
            //队列头部就是该窗口最大的！
            if((i + 1) >= size)
                ret.push_back(num[deq.front()]);
        }
        return ret;
    }
};

int maxValue(int arr[], int begin, int window){
 int max = INT_MIN;
 int end = begin + window;
 for(int i = begin; i < end; i++){
 if(max < arr[i]){
 max = arr[i];
 }
 }
 return max;
}
vector<int> windowValue(int arr[], int n, int window){
 vector<int> result;
 int end = n - window + 1;
 for(int i=0; i < end; i++){
 result.push_back(maxValue(arr, i, window));
 }
 return result;
}

import java.util.*;

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        if(num == null || size == 0 || size > num.length) {
            return new ArrayList<Integer>();
        }
        int windowNum = num.length - size + 1;
        LinkedList<Integer> list = new LinkedList<>();
        ArrayList<Integer> res = new ArrayList<>();
        int maxTmp = Integer.MIN_VALUE;
        for(int i = 0; i < windowNum; i++) {
            maxTmp = num[i];
            for (int j = 1; j < size; j++) {
                maxTmp = num[i+j] > maxTmp ? num[i+j] : maxTmp;
            }
            res.add(maxTmp);
        }
        return res;
    }
}

#python2.7 O(n) 时间24ms 内存5760k
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        length = len(num)
        if size<=0 or size>length:return []
        i = 0
        ans =[max(num[:size])]
        while size+i < length:
            if num[i]<ans[-1]:
                ans.append(max([ans[-1],num[i+size]]))
            else:
                ans.append(max(num[i+1:i+size+1]))
            i+=1
        return ans

public ArrayList<Integer> maxInWindows(int[] num, int size) {
		ArrayList<Integer> maxWindows = new ArrayList<>();
		// 特殊情况处理
		if (num.length == 0 || num == null || num.length < size) {
			return maxWindows;
		}

		if (num.length >= size && size >= 1) {
			// 用来保存可能是滑动窗口最大值的数字的下标
			ArrayDeque<Integer> indexDeque = new ArrayDeque<>();

			for (int i = 0; i < size; i++) {
				// 如果已有数字小于待存入的数据，
				// 这些数字已经不可能是滑动窗口的最大值
				// 因此它们将会依次地从队尾删除
				while (!indexDeque.isEmpty() && num[i] >= num[indexDeque.getLast()]) {
					indexDeque.pollLast();
				}

				indexDeque.addLast(i);
			}

			for (int i = size; i < num.length; i++) {
				maxWindows.add(num[indexDeque.getFirst()]);
				// 如果已有数字小于待存入的数据，
				// 这些数字已经不可能是滑动窗口的最大值
				// 因此它们将会依次地从队尾删除
				while (!indexDeque.isEmpty() && num[i] >= num[indexDeque.getLast()]) {
					indexDeque.pollLast();
				}
				// 如果队列的头部元素已经从滑动窗口里滑出，滑出的数字需要从队列的头部删除
				if (!indexDeque.isEmpty() && indexDeque.getFirst() <= (i - size)) {
					indexDeque.pollFirst();
				}

				indexDeque.addLast(i);
			}
			maxWindows.add(num[indexDeque.getFirst()]);
		}
		return maxWindows;

	}

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    ArrayList<Integer> maxInWindows(int [] num, int size)
    {
            int[] m_Seq=new int[size];

             ArrayList m_MaxSet=new ArrayList(); 
        
            if (num.length < size) return m_MaxSet;
        
            if (size==0) return m_MaxSet;

            for(int i=0;i<=num.length-size;i++){

                m_Seq = Arrays.copyOfRange(num,i,i+size);

                Arrays.sort(m_Seq);

                m_MaxSet.add(m_Seq[m_Seq.length-1]);

            }
        
            return m_MaxSet;
    }
}

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> list=new ArrayList<Integer>();//用来放每个滑窗的max
        if(num.length==0||size==0){return list;}
        for(int i=0;i<=num.length-size;i++){
            int[] arr=new int[size];
            int j=0,k=i;
            while(j<=size-1){
                arr[j++]=num[k++];
            }
            list.add(Max(arr));
        }
        return list;
    }
    public int Max(int[] array){
        int max=array[0];
        for(int i=0;i<=array.length-1;i++){
            if(array[i]>max){
                max=array[i];
            }
        }
        return max;
    }
}

双端队列
时间复杂度：O(n) 空间复杂度：O(k) k为窗口大小

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        res = []
        dq = []
        for i in range(len(num)):
            while dq and num[dq[-1]] < num[i]:
                dq.pop()
            dq.append(i)
            if i - dq[0] >= size:
                dq.pop(0)
            if i + 1 >= size:
                res.append(num[dq[0]])
        return res

function maxInWindows(num, size)
{
    if(num.length<size||size===0) return []
    
    //第一个最大的
    let max=Math.max(...num.slice(0,size))
    let maxlist=[max]
    for(let i=size;i<num.length;i++){ 
        //大于最大值就记录
        if(num[i]>max){
            max=num[i] 
        }
        //左边界是最大就重新计算最大值
        else if(max==num[i-size]) max=Math.max(...num.slice(i-size+1,i+1))
        maxlist.push(max)
    }
    return maxlist
}

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        # write code here
        # 不满足条件时为空
        if size==0&nbs***bsp;len(num)<size:
            return []
        # 可以生成的组数
        groups=len(num)+1-size
        res=[]
        for i in range(groups):
            # i:size+i保证每次取size个大小
            res.append(max(num[i:size+i]))
        return res

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> vec;
        for(int i=0;i+size-1<num.size();i++){
            int x = num[i];
            for(int j=i;j<=i+size-1;j++){
                x = max(num[j],x);
            }
            vec.push_back(x);
        }
        return vec;
    }
};