`

Sliding Window Maximum

阅读更多
Sliding Window Maximum
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
1 [3  -1  -3] 5  3  6  7       3
1  3 [-1  -3  5] 3  6  7       5
1  3  -1 [-3  5  3] 6  7       5
1  3  -1  -3 [5  3  6] 7       6
1  3  -1  -3  5 [3  6  7]      7
return [3,3,5,5,6,7]

题目的意思是给定一个数组,一个长度为k的滑动窗口,从数组的最左边滑动到最右边,每次移动一个位置,找出每次窗口中最大的元素。这道题我们可以通过维护一个最大值的下标maxIndex,和一个最大值max来解决。遍历数组,每当窗口滑动后,我们通过最大值的下标来判断最大值元素是否还在窗口中,如果在,就只比较最大值和当前值就可以,做相应的处理;如果最大值元素不在窗口中,那我们就从这个窗口中找出最大值,时间复杂为O(k),这样总的时间复杂度为O(nk)。代码如下:
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0) return new int[0];
        if(k == 1) return nums;
        int maxIndex = 0;
        int max = Integer.MIN_VALUE;
        int index = 0;
        int[] result = new int[nums.length - k + 1];
        
        for(int i = 0; i < nums.length - k + 1; i++) {
            if(i == 0 || maxIndex == i - 1) {
                max = Integer.MIN_VALUE;
                for(int j = i; j < i + k; j++) {
                    if(nums[j] > max) {
                        max = nums[j];
                        maxIndex = j;
                    }
                }
            } else {
                if(nums[i + k - 1] > max) {
                    max = nums[i + k - 1];
                    maxIndex = i + k - 1;
                }
            }
            result[index ++] = max;
        }
        return result;
    }
}
分享到:
评论

相关推荐

    alienxcn#ZXBlog#LintCode - 362. Sliding Window Maximum滑动窗口的最大值1

    再判断3位置上的2,由于比1大(也就是队列的尾部比这个数小),所以把队列尾部弹出一个,1弹出,由于4比2大,就可以放2了:再看窗口中减数的逻辑,当L向右移动的时

    lrucacheleetcode-leetcode:leetcode

    Maximum 255. Verify Preorder Sequence in Binary Search Tree 907. Sum of Subarray Minimums 二叉搜索树 99. Recover Binary Search Tree 109. Convert Sorted List to Binary Search Tree 116. Populating Next ...

    leetcode信封-LeetCode:LeetCode解题

    leetcode信封 LeetCode LeetCode解题 源码目录 //main下为源码,test下为单元测试 │ src │ ├─main │ └─java │ └─com │ └─algorithm │ GeneratorParenthesis.java //22. ...Sliding Window Maximum

    LeetCode最全代码

    318| [Maximum Product of Word Lengths](https://leetcode.com/problems/maximum-product-of-word-lengths/) | [C++](./C++/maximum-product-of-word-lengths.cpp) [Python](./Python/maximum-product-of-word-...

    计算机安全与密码学 Computer.Security.And.Cryptography.

    Model from Sliding Window Counts 34 2.8 Markov Scoring 34 2.9 The ADFGVX Transposition System 47 2.10 CODA 49 2.11 Columnar Transposition Problems 50 CHAPTER 3 MONOALPHABETIC SUBSTITUTION 3.1 ...

    leetcode双人赛-LeetCode:力码

    Sliding Window,滑动窗口类型 滑动窗口类型的题目经常是用来执行数组或是链表上某个区间(窗口)上的操作。比如找最长的全为1的子数组长度。滑动窗口一般从第一个元素开始,一直往右边一个一个元素挪动。当然了,...

    信息论基础(英文版)

    13.4.1 Sliding Window Lempel–Ziv Algorithm 441 13.4.2 Tree-Structured Lempel–Ziv Algorithms 442 13.5 Optimality of Lempel–Ziv Algorithms 443 13.5.1 Sliding Window Lempel–Ziv Algorithms 443 13.5.2 ...

    algorithm-homework

    作业说明 代码注释中有力扣链接. ...滑动窗口最大值, sliding-window-maximum.ts 两两交换链表中的节点, swap-nodes-in-pairs.ts 三数之和, three-sum.ts 接雨水, trapping-rain-water.ts 两数之和,

    i-vector的工具箱

    The normalization is performed over a sliding window that typically spans 301 frames (that is 3 seconds at a typical 100 Hz frame rate). The middle frame in the window is normalized based on the mean ...

    leetcode题库-Leetcode-Summary:Leetcode刷题总结(Java版)——更新中

      滑动窗口的最大值(Maximum_value_of_sliding_window.java)   包含min函数的栈(The_stack_containing_the_min_function.java)   队列的最大值(The_maximum_value_of_the_queue.java) 堆(heap_items) ...

    ACM算法模板和pku代码

    Sliding Window 数据结构 线段树 Cows 线段染色 排队问题 第K大的数 离散化+线段树 灯光投影 网络赛取连续子序列问题 线段树+树状数组+并查集,转化为排队问题 离散化 离散化矩形切割,矩形覆盖面积统计 ...

    Competitive Programmer's Handbook Antti Laaksonen

    8.3 Sliding window minimum . . . . . . . . . . . . . . . . . . . . . . . . . 81 9 Range queries 83 9.1 Static array queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 9.2 Binary ...

    通过修改后的LeNet进行蒙面人脸检测

    近来,在野外发现蒙面人脸的方法已经兴起,其应用范围很广,从暴力视频检索到视频监视。 主要由于低分辨率和任意视角的困难以及收集足够数量的训练样本的局限性,其准确检测仍然是一个未解决的问题。...

    Visual C++ 编程资源大全(英文源码 控件)

    08.zip Drop down a popdown window instead of a dropdown list from a combobox 在ComboBox中用Drop down方式代替dropdown list方式(32KB)&lt;END&gt;&lt;br&gt;9,09.zip Change listbox width of combo boxes 在...

Global site tag (gtag.js) - Google Analytics