239. 滑动窗口最大值

本篇文章分享239. 滑动窗口最大值，对你有帮助的话记得收藏一下，看Java资料网收获更多编程知识

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

解题思路

这里我们可以自己设计个队列，这个队列里面主体数据结构我们使用Java里的Deque这个双向队列，我们向这个队列里放入元素的时候我们的原则是只维持队列里面最大的元素在我们这个双向队列的头部位置，当我们的滑动窗口向后滑动的时候，如果此时我们要弹出的元素不是队列的头部元素我们就直接跳过(说明在此前添加进来的时候就被pass掉了)，如果我们此时要弹出的元素是队列的头部元素，我们就要把头部元素弹出，然后向后依次遍历就可以了，主体思路就是我们只维持最大的元素在我们队列的头部就行了

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        List<Integer> result = new ArrayList<>();

        MyQueue queue = new MyQueue();

        for (int i = 0; i < k; i++) {
            queue.push(nums[i]);
        }
        result.add(queue.getMax());

        for (int j = k; j < nums.length; j++) {
            queue.pop(nums[j - k]);
            queue.push(nums[j]);
            result.add(queue.getMax());
        }

        int[] num = result.stream().mapToInt(Integer::intValue).toArray();
        return num;

    }

    class MyQueue {
        Deque<Integer> deque = new LinkedList<>();

        public void pop(int value) {
            if (!deque.isEmpty() && deque.getFirst() == value) {
                deque.pollFirst();
            }
        }
        
        public void push(int value) {
            while (!deque.isEmpty() && deque.getLast() < value) {
                deque.pollLast();
            }
            deque.addLast(value);
        }

        public int getMax() {
            return deque.getFirst();
        }

    }

}

文章来源:https://www.cnblogs.com/dfj-blog/p/18375756
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！