“LeetCode” refers to Offer 59-i. Maximum number of sliding Windows

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Title: Finger Offer 59 – I. Sliding window maximum – LeetCode (leetcode-cn.com)

Preface ✔ :

Algorithm, for front-end people both familiar and unfamiliar, familiar is that each front-end ER has to learn algorithm to deal with the interview, work and examination, unfamiliar is that we usually use algorithm in the work is not a lot of places. So, we’ve always wanted to ask whether algorithms are important to the front end.

The answer is yes, N.Wirth (Wirth) said, “program = algorithm + data structure” of course does not mean that we can write a good program if we master data structure and algorithm, just like composition = grammar + words does not mean that we can write a good composition if we master the latter.

The point is that it’s hard to write good programs without data structures and algorithms, and the most important thing is that it’s hard to understand the author’s intention when reading the source code of some good projects, so our vision is limited.

One of the souls of computer science is algorithms, so if we want to go to the next level, it is essential to learn and master algorithms and data structures

If it is helpful, please give me a like and I will be very happy 😊

The title 🚩

Given an array nums and the size k of the sliding window, find the maximum number of sliding Windows.

Difficulty: Medium

Example:

Input:

Eight, three, one, three, three, five, three, six, sevenCopy the code

Output:

3, 3, 5, 5, 6, 7Copy the code

Their thinking

Violence:

  1. Define window size K
  2. After that, the maximum value of the window is obtained through the cycle
  3. Move the window, repeat2operation

The resulting program is order k times n.

Through queue optimization:

  1. Define window size K

  2. Create a queue

  3. Scan each number one by one, if the next number to be scanned is greater than the last n number in the queue, remove the last n number and insert the number to be scanned else Add the number to be scanned to the end of the queue, if the position of the head of the queue is outside the window pair the head of the queue

  4. When the number of scanned data equals the size of the window, the queue header is the maximum value of the window

Optimization algorithm diagram 🎁

Now let me give you another example that’s easier to use

Input:

5, 2, 1, 3, minus 1, 5, 2Copy the code

This is the change in our queue as we scan the data one by one, so let’s parse it one by one.

  1. A [0], queue has no element, can be directly inserted
  2. A [1], the queue has only 1 data, smaller than a[1], delete a[0] and insert a[1], at this time, the scanned data is equal to the size of the window, so the queue head is directly output
  3. A [2], the queue has 3 data, no data in the queue is smaller than a[2], directly inserted into the queue, and output queue head
  4. A [3], the queue has 3 and 1 data, but data 3 is already outside the window, and 3 is removed from the queue. At this time, there is no number smaller than A [3], so it is directly inserted into the end of the queue and output the head of the queue

I’ll leave the fifth step to the reader, and I’m sure you’ve seen the algorithm here, which is essentially a monotonic queue.

Code 🔥

class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> q ; vector<int> C; int hh = 0, tt = -1; for(int i = 0; i < nums.size(); i++) { if(hh <= tt && i - k + 1 > q[hh]) hh++; while(hh <= tt && nums[i] > nums[q[tt]]) tt--; q[++tt] = i; ++tt; if(i - k + 1 >= 0) C.push_back(nums[q[hh]]); } return C; }};Copy the code

Conclusion 😉

So that’s the end of lemon’s algorithmic tutorial. If you’d like to explore, learn about the front end or mess around with it, please add wechat gyjMy2517.

If helpful, please support a like it 🎈