# Simple concept of sliding window

Sliding window is a hypothetical data structure. The window we implement in this article can quickly find the maximum and minimum value of the interval

The operation efficiency is also excellent in some problems that do not go back in the interval

Set the left boundary of the window as l and the right boundary as r, (it is specified that l < = r is constant)

We can enter the number from the right side of the window by sliding the right boundary

You can also slide the left border to show the number from the left side of the window

# Sliding window for interval maximum (leetcode239)

Title Description:

Give you an integer array nums, with a sliding window of size k moving from the leftmost side of the array to the rightmost side of the array. You can only see k numbers in the sliding window. The sliding window moves only one bit to the right at a time.
Returns the maximum value in the sliding window.

Thinking solution

We can realize the structure of our maximum window through the double ended queue, which stores the subscripts in the array

The order of the number corresponding to the subscript must always be maintained in the double ended queue

Keep moving the window. If the number of entries will break the balance from large to small (that is, the new number is greater than the end of the queue), the number will continue to appear at the end of the queue until the requirements of the double ended queue are met, and then insert the current number

Dynamic diagram demonstration:

It can be expressed in a fixed size window. As long as the window contains this number, the maximum value of this window will always be the top of the queue

Until there is no maximum value in the window, pop it up from the left

```class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n=nums.size();
vector<int>ans;

deque<int>qmax;//Maintain maximum queue
for(int r=0;r<n;r++)
{
while(!qmax.empty()&&nums[qmax.back()]<=nums[r])
{
qmax.pop_back();//This is the structure of maintaining the queue from large to small
//Pop up all numbers smaller than the new number at the end of the team
}
qmax.push_back(r);

if(qmax.front()==r-k)
{
qmax.pop_front();//This is the case where the subscript corresponding to the maximum value is no longer in the window
//Because r-l=k
}

if(r>=k-1)
{
ans.push_back(nums[qmax.front()]);
//When the window is formed, add the number directly
}
}
return ans;
}
};
```

# Find the number of subarrays that meet the requirements

Title Description:

Given an array arr and an integer sum

If a subarray (which must be connected) meets the maximum minimum value < = sum of the subsequence, it is said that the subarray meets the requirements

Returns the number of subsequences that meet the requirements

Solution ideas:

We can draw two conclusions first:

• If a subarray meets the requirements, all subarrays of this subarray meet the requirements
• If a subarray does not meet the requirements, the arrays with it as a subarray do not meet the requirements

Why?

We know that our final requirement is Max min

If the requirements are met, then max min < sum should be established

Obviously, it is easy to see that the maximum value of its sub array will only be smaller than the maximum value of this array, and the minimum value will only be larger than the minimum value of this array,

So in this case, max min will only decrease

The same can be proved if the requirements are not met

So we can:

Initially, put the window to the left, maintain the maximum and minimum values of the window, and constantly update the right boundary of the window until it does not meet the requirements

According to conclusion 1, all subarrays starting from L meet the requirements * * (subarrays from L to l+1;l to l+2;l to l+3...)**

According to conclusion 1, we can update l without updating r

```	int AllLessNumSubArray(vector<int>& nums, int sum)
{
int n = nums.size();
deque<int>qmax;
deque<int>qmin;
int ans = 0;
int r = 0;
for (int l = 0; l < n; l++)
{
while (r < n)
{
while (!qmax.empty() && nums[qmax.back()] <= nums[r])
{
qmax.pop_back();
}

qmax.push_back(r);
while (!qmin.empty() && nums[qmin.back()] >= nums[r])
{
qmin.pop_back();
}
qmin.push_back(r);
//The above is to maintain the maximum and minimum queue
//The following is the sliding window

if (nums[qmax.front()] - nums[qmin.front()] <= sum)
{
r++;
}
else
{
break;
}

}

ans += r - l;
//Update expired elements
if (qmax.front() == l)
{
qmax.pop_front();
}

if (qmin.front() == l)
{
qmin.pop_front();
}
}
return ans;
}
```

The above questions clearly require the maximum and minimum value of the window. The following question is not obvious

# The best starting point of gas station

Title Description

Here are two arrays, gas and cost

In fact, gas[i] refers to the fuel consumption of No. I gas station, and cost[i] refers to the fuel consumption from No. I to i+1 gas station

The initial fuel volume of the vehicle is 0

Returns a bool type, which indicates whether the car can complete a circle when starting from No. i gas station, and can only make a circle counterclockwise

For example:

gas=[1,1,3,1]
cost=[2,2,1,1]

The figure is as follows:

If you start from gas station 0, cost[0] is 2, but gas[0]=1, the car can't get to gas station 1, so ans[0] returns false

Overall return: [0,0,1,0]

Solution ideas:

We can do a processing before solving the problem

First, subtract the number corresponding to each position of gas and cost to obtain the processed array nums

```for (int i = 0; i < n; i++)
{
nums[i] = gas[i] - cost[i];
}
```

In this way, we can show whether we can get to the next station from a certain station. If the result is negative, we can't get there

We can find the prefix sum. If there is a negative number halfway, it means that this circle cannot be completed

For example, the prefix and starting from 0 indicate the amount of remaining fuel passing through each gas station halfway from 0
The prefix and starting from 1 indicate starting from 1, and so on

Because we have to go around, we should deal with twice the size of the original array (don't start from 0?)

```		int m=n<<1;
for (int i = 0; i < n; i++)
{
nums[i] = gas[i] - cost[i];
nums[i + n] = gas[i] - cost[i];
}

for (int i = 1; i < m; i++)
{
nums[i] += nums[i - 1];
}
```

The size of the window in this question is required to be the same as that of the original array. We can deal with our array as follows:

Maintain minimum window

Obviously, if the minimum value is not negative, there is no negative number in the window

When updating the array window, we remember to subtract the value in the window from the value in front of the left boundary of the window, so as to be the correct prefix and prefix starting from l

Directly judge whether the current minimum value is less than 0

Code is comment:

```	vector<bool> GasStation(vector<int>& gas, vector<int>& cost)
{
int n = gas.size();
int m = n << 1;
vector<bool>ans(n, false);
int* nums = new int[m];

for (int i = 0; i < n; i++)
{
nums[i] = gas[i] - cost[i];
nums[i + n] = gas[i] - cost[i];
}

for (int i = 1; i < m; i++)
{
nums[i] += nums[i - 1];
}

deque<int>w;

//Initialization window
for (int i = 0; i < n; i++)
{
while (!w.empty() && nums[w.back()] >= nums[i])
{
w.pop_back();
}
w.push_back(i);
}

for (int offset = 0, i = 0, j = n; j < m; offset = nums[i++], j++)
{
//offset represents the number in front of the window and w always maintains the minimum value of the window
//i left boundary, j right boundary

if (nums[w.front()] - offset >= 0)
{
ans[i] = true;
}

if (w.front() == i)
{
w.pop_front();
}

while (!w.empty() && nums[w.back()] >= nums[j])
{
w.pop_back();
}
w.push_back(j);

}
delete[]nums;
return ans;
}
```

Keywords: Algorithm data structure leetcode

Added by parboy on Wed, 23 Feb 2022 17:27:24 +0200