美文网首页
ORID56 max of sliding window

ORID56 max of sliding window

作者: Wilbur_ | 来源:发表于2020-09-21 06:20 被阅读0次
    1. max of sliding window 解题报告
      这道题算经典了,因为很多笔试或者OA都会考到相关类型的题目。
      这道题就给你两个input, 一个数组,一个window size k (intput:int[] nums, int k)
      要输出的值就是每个window里面最大值组成的数组。
      那么首先要想到的就是先建立一个返回的数组,这个数组的大小应该是nums.length - k + 1
    int[] res = new int[nums.length - k + 1];
    

    用什么算法?

    这道题实际上就是sliding window的一道题,sliding window本身就是一种解决问题的形式。不过这道题有一个很好地优化空间,你不必像sliding window本身那样每次把数组中的k个数取出来,然后存最大值,因为这样会导致时间复杂度变为O(NK),而利口上面正好有一个很大的test case,所以会超时。
    这道题能够节省时间复杂度的方式使用Deque,因为你可以在滑动窗口的时候直接把超出窗口空间的数字剔除,并且对比最后一个数字和即将放入队列的数字,如果比即将要进入队列的数字要小,那么就把最后一个数字去掉,这样deque里面第一个数就是当前最大的数。
    而怎么保证你滑动窗口把超出窗口大小的数去掉?
    用deque来存index*
    这是很重要的一步,因为如果你存的是数字,那就没法判断当前第一个数是否是超出窗口大小的index了。
    一个比较重要的地方是deque在Java里面是通过ArrayDeque来实现的。
    下面是代码

        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums == null) {
                return new int[0];
            }
            int[] res = new int[nums.length - k + 1];
            Deque<Integer> dq = new ArrayDeque<>();
            for (int i = 0; i < nums.length; i++) {
                if (!dq.isEmpty() && dq.peek() < i - k + 1) {
                    dq.pollFirst();
                }
                while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
                    dq.pollLast();
                }
                dq.offer(i);
                if (i >= k-1) {
                    res[i-k+1] = nums[dq.peek()];
                }
            }
            return res;
        }
    

    时空复杂度

    O(N)要走n次
    O(K)deque的大小最大可能就是k,所以空间复杂度是k

    相关文章

      网友评论

          本文标题:ORID56 max of sliding window

          本文链接:https://www.haomeiwen.com/subject/espsektx.html