Table of Contents
Problem description" >Problem description
Analysis" >Analysis
Home Web Front-end JS Tutorial Algorithm to realize the maximum value of sliding window in js

Algorithm to realize the maximum value of sliding window in js

Jul 21, 2018 am 11:03 AM
javascript front end algorithm

This article shares with you the algorithm for realizing the maximum value of the sliding window in js. The content is very good. Friends in need can refer to it. I hope it can help everyone.

Problem description

Given an array and the size of the sliding window, find the maximum value of all values ​​in the sliding window. For example, if the input array is {2,3,4,2,6,2,5,1} and the size of the sliding window is 3, then there are a total of 6 sliding windows, and their maximum values ​​are {4,4,6, 6,6,5}; There are the following 6 sliding windows for the array {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}, {2,3,4,2,6,[2,5, 1]}.

Analysis

Think carefully, for the array {2,3,4,2,6,2,5,1}, if the window size is 3 , then the whole process is as follows:

  1. {[2,3,4],2,6,2,5,1}, the maximum value at this time is 4

  2. {2,[3,4,2],6,2,5,1}, the maximum value at this time is 4

  3. {2, 3,[4,2,6],2,5,1}, the maximum value at this time is 6, because the newly entered window 6 is larger than 4

  4. {2,3 ,4,[2,6,2],5,1}, the maximum value at this time is 6

  5. {2,3,4,2,[6,2,5] ,1}, the maximum value at this time is 6

  6. ##{2,3,4,2,6,[2,5,1]}, the maximum value at this time is 5

The idea is:


Save the array subscript maxIndex of the maximum value of the current window, slide the window once, if maxIndex is still in the window, you only need to compare maxIndex Which one is greater than the value of the latest entry into the window? If the newly entered value is greater, update maxIndex, otherwise there is no need to update; if maxIndex is not within the window, all values ​​in the current window must be traversed to find the new maxIndex

Code implementation
function maxInWindows(arr, size)
{
    if(size > arr.length || size === 0)
        return [];
    var res = [], maxIndex = -1;
    for(var l = 0, r = size-1;r < arr.length;l++, r++){
        if(maxIndex < l){
            maxIndex = getMaxIndex(arr, l, r);
        }
        if(arr[r] > arr[maxIndex]){
            maxIndex = r;
        }
        res.push(arr[maxIndex]);
    }

    return res;
}
function getMaxIndex(arr, l, r){
    var index = l;
    for(var i = l;i <= r;i++) {
        if(arr[i] > arr[index])
            index = i;
    }
    return index;
}
Copy after login

Related recommendations:

Using two stacks to implement the queue algorithm in js

## How to use the $() function in jquery

The above is the detailed content of Algorithm to realize the maximum value of sliding window in js. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

CLIP-BEVFormer: Explicitly supervise the BEVFormer structure to improve long-tail detection performance CLIP-BEVFormer: Explicitly supervise the BEVFormer structure to improve long-tail detection performance Mar 26, 2024 pm 12:41 PM

Written above &amp; the author’s personal understanding: At present, in the entire autonomous driving system, the perception module plays a vital role. The autonomous vehicle driving on the road can only obtain accurate perception results through the perception module. The downstream regulation and control module in the autonomous driving system makes timely and correct judgments and behavioral decisions. Currently, cars with autonomous driving functions are usually equipped with a variety of data information sensors including surround-view camera sensors, lidar sensors, and millimeter-wave radar sensors to collect information in different modalities to achieve accurate perception tasks. The BEV perception algorithm based on pure vision is favored by the industry because of its low hardware cost and easy deployment, and its output results can be easily applied to various downstream tasks.

Implementing Machine Learning Algorithms in C++: Common Challenges and Solutions Implementing Machine Learning Algorithms in C++: Common Challenges and Solutions Jun 03, 2024 pm 01:25 PM

Common challenges faced by machine learning algorithms in C++ include memory management, multi-threading, performance optimization, and maintainability. Solutions include using smart pointers, modern threading libraries, SIMD instructions and third-party libraries, as well as following coding style guidelines and using automation tools. Practical cases show how to use the Eigen library to implement linear regression algorithms, effectively manage memory and use high-performance matrix operations.

Explore the underlying principles and algorithm selection of the C++sort function Explore the underlying principles and algorithm selection of the C++sort function Apr 02, 2024 pm 05:36 PM

The bottom layer of the C++sort function uses merge sort, its complexity is O(nlogn), and provides different sorting algorithm choices, including quick sort, heap sort and stable sort.

Can artificial intelligence predict crime? Explore CrimeGPT's capabilities Can artificial intelligence predict crime? Explore CrimeGPT's capabilities Mar 22, 2024 pm 10:10 PM

The convergence of artificial intelligence (AI) and law enforcement opens up new possibilities for crime prevention and detection. The predictive capabilities of artificial intelligence are widely used in systems such as CrimeGPT (Crime Prediction Technology) to predict criminal activities. This article explores the potential of artificial intelligence in crime prediction, its current applications, the challenges it faces, and the possible ethical implications of the technology. Artificial Intelligence and Crime Prediction: The Basics CrimeGPT uses machine learning algorithms to analyze large data sets, identifying patterns that can predict where and when crimes are likely to occur. These data sets include historical crime statistics, demographic information, economic indicators, weather patterns, and more. By identifying trends that human analysts might miss, artificial intelligence can empower law enforcement agencies

PHP and Vue: a perfect pairing of front-end development tools PHP and Vue: a perfect pairing of front-end development tools Mar 16, 2024 pm 12:09 PM

PHP and Vue: a perfect pairing of front-end development tools. In today's era of rapid development of the Internet, front-end development has become increasingly important. As users have higher and higher requirements for the experience of websites and applications, front-end developers need to use more efficient and flexible tools to create responsive and interactive interfaces. As two important technologies in the field of front-end development, PHP and Vue.js can be regarded as perfect tools when paired together. This article will explore the combination of PHP and Vue, as well as detailed code examples to help readers better understand and apply these two

Improved detection algorithm: for target detection in high-resolution optical remote sensing images Improved detection algorithm: for target detection in high-resolution optical remote sensing images Jun 06, 2024 pm 12:33 PM

01 Outlook Summary Currently, it is difficult to achieve an appropriate balance between detection efficiency and detection results. We have developed an enhanced YOLOv5 algorithm for target detection in high-resolution optical remote sensing images, using multi-layer feature pyramids, multi-detection head strategies and hybrid attention modules to improve the effect of the target detection network in optical remote sensing images. According to the SIMD data set, the mAP of the new algorithm is 2.2% better than YOLOv5 and 8.48% better than YOLOX, achieving a better balance between detection results and speed. 02 Background & Motivation With the rapid development of remote sensing technology, high-resolution optical remote sensing images have been used to describe many objects on the earth’s surface, including aircraft, cars, buildings, etc. Object detection in the interpretation of remote sensing images

Application of algorithms in the construction of 58 portrait platform Application of algorithms in the construction of 58 portrait platform May 09, 2024 am 09:01 AM

1. Background of the Construction of 58 Portraits Platform First of all, I would like to share with you the background of the construction of the 58 Portrait Platform. 1. The traditional thinking of the traditional profiling platform is no longer enough. Building a user profiling platform relies on data warehouse modeling capabilities to integrate data from multiple business lines to build accurate user portraits; it also requires data mining to understand user behavior, interests and needs, and provide algorithms. side capabilities; finally, it also needs to have data platform capabilities to efficiently store, query and share user profile data and provide profile services. The main difference between a self-built business profiling platform and a middle-office profiling platform is that the self-built profiling platform serves a single business line and can be customized on demand; the mid-office platform serves multiple business lines, has complex modeling, and provides more general capabilities. 2.58 User portraits of the background of Zhongtai portrait construction

Questions frequently asked by front-end interviewers Questions frequently asked by front-end interviewers Mar 19, 2024 pm 02:24 PM

In front-end development interviews, common questions cover a wide range of topics, including HTML/CSS basics, JavaScript basics, frameworks and libraries, project experience, algorithms and data structures, performance optimization, cross-domain requests, front-end engineering, design patterns, and new technologies and trends. . Interviewer questions are designed to assess the candidate's technical skills, project experience, and understanding of industry trends. Therefore, candidates should be fully prepared in these areas to demonstrate their abilities and expertise.

See all articles