The sliding window
The essence of a sliding window is a double pointer, using a left pointer and a right pointer to form a window. Windows should have the following features:
- The element relationships in the window satisfy one of the constraints given by the problem
- A valid window can provide a possible solution to the problem
In general, the index relationship between window types and pointer initials is as follows:
- Fixed size window (set size to K) :
left = 0, right = k-1 - Variable size window:
left = 0, right = 0
Left and right pointer movement mode:
rightPointer: Active right moveleftPointer: when[left, right]When the window does not meet the requirements, the passive right move
The basic problem solving template of sliding window is:
// nums is a given interval, usually k is a window qualifier
function slidingWindow(nums, k) {
let result = 0
let left = 0
let right = 0
// Some relation within the window, here is and
let sum = 0
while (right < nums.length) {
// Maintain some relationship within the window
sum += nums[right]
// The left pointer moves to the right passively when the relationship between elements in the window does not meet one of the constraints given in the question
while (sum < k) {
// Maintain some relationship within the window
sum -= nums[left]
left++
}
// A valid window can provide a possible solution to the problem
result = Math.max(result, right - left + 1)
right++
}
return result
}
Copy the codeIn Leetcode, sliding window topics are classified as follows:
Basic template questions, as an appetizer:
- 1004
- 1208
- 1456
On top of the template, there is a bit more deformation:
- 1423
- 1658
- 978
Combination type:
- 1498: Sliding window + math
- 3: sliding window + hash table
- 239: Sliding window + monotone queue
- 1438: Sliding window + 2 monotonic queues
- 480: Sliding window + heap
You can directly click the subtitle to enter the corresponding Leetcode page. It is recommended to swipe the questions in the order above
Leetcode 1004 – Medium
参 考 答 案 :
Sliding window standard template problem, template can be understood
Implementation:
function longestOnes(nums, k) {
let result = 0
let left = 0
let right = 0
while (right < nums.length) {
if (nums[right] === 0) {
k--
}
while (k < 0) {
if (nums[left] === 0) {
k++
}
left++
}
result = Math.max(result, right - left + 1)
right++
}
return result
}
Copy the codeLeetcode 1208 – Medium
Answer:
Sliding window standard template problem, template can be understood
Implementation:
function equalSubstring(s, t, maxCost) {
let result = 0
let left = 0
let right = 0
while (right < s.length) {
maxCost -= Math.abs(s[right].charCodeAt() - t[right].charCodeAt())
while (maxCost < 0) {
maxCost += Math.abs(s[left].charCodeAt() - t[left].charCodeAt())
left++
}
result = Math.max(result, right - left + 1)
right++
}
return result
}
Copy the codeLeetcode 1456 – Medium
Answer:
Sliding window standard template problem, template can be understood
Implementation:
function maxVowels(s, k) {
const vowelsMap = {
a: 1.e: 1.i: 1.o: 1.u: 1
}
// Select the first k values as initial values
let vowels = 0
for (let i = 0; i < k; i++) {
if (s[i] in vowelsMap) {
vowels++
}
}
let maxVowels = vowels
/ / right movement
for (let i = k; i < s.length; i++) {
/ / judgment
if (s[i] in vowelsMap) {
vowels++
}
/ / determine
if (s[i - k] in vowelsMap) {
vowels--
}
maxVowels = Math.max(maxVowels, vowels)
}
return maxVowels
}
Copy the codeLeetcode 1423 – Medium
Answer:
Fixed size window
“For each action, you can pick up a card from the beginning or the end of the row, and you must end up with exactly K cards.” It can be converted to maintaining a window with the size of cardPoints. Length -k. Find the minimum value that can be obtained by sliding this window to the right to obtain the maximum value of remaining cards
Implementation:
function maxScore(cardPoints, k) {
const totalSum = cardPoints.reduce((acc, val) = > acc += val, 0)
const windowSize = cardPoints.length - k
// Select the former windowSize as the initial value
let sum = 0
for (let i = 0; i < windowSize; i++) {
sum += cardPoints[i]
}
let minSum = sum
// Start sliding to the right
for (let i = windowSize; i < cardPoints.length; i++) {
// Find the difference between one in and one out
sum += cardPoints[i] - cardPoints[i - windowSize]
minSum = Math.min(minSum, sum)
}
return totalSum - minSum
}
Copy the codeLeetcode 1658 – Medium
Answer:
Variable size window
“On each operation, you should remove the leftmost or rightmost element of the array nums” => find a contiguous window where the elements and = sum -x
Implementation:
function minOperations(nums, x) {
// find the sum of arrays
let sum = 0
for (let i = 0; i < nums.length; i++) {
sum += nums[i]
}
const windowSumTarget = sum - x
// If the sum of the target elements is less than 0, return it directly
if (windowSumTarget < 0) {
return -1
}
// find a continuous window with elements and = sum -x
let left = 0
let right = 0
let operateCount = Number.MAX_VALUE
let windowSum = 0
while (right < nums.length) {
windowSum += nums[right]
while (windowSum > windowSumTarget) {
windowSum -= nums[left]
left++
}
if (windowSum === windowSumTarget) {
operateCount = Math.min(operateCount, nums.length - (right - left + 1))
}
right++
}
return operateCount === Number.MAX_VALUE ? -1 : operateCount
}
Copy the codeLeetcode 978 – Medium
Answer:
This question, the title is more difficult to understand, but it is a more typical template question
Implementation:
function maxTurbulenceSize(arr) {
let result = 1
let left = 0
let right = 0
while (right < arr.length - 1) {
if (left === right) {
if (arr[left] === arr[left+1]) {
left++
}
right++
} else {
if (arr[right-1] < arr[right] && arr[right] > arr[right+1]) {
right++
} else if (arr[right-1] > arr[right] && arr[right] < arr[right+1]) {
right++
} else {
left = right
}
}
result = Math.max(result, right - left + 1)}return result
}
Copy the codeLeetcode 1498 – Medium
Answer:
Experience: involving “mod 10^9 + 7” and power, the power table is preprocessed first
Mathematics knowledge: Recursive formula of combinatorial number formula C (n,0) + C (n,1) + C (n,2) +…… Plus c of n,n is equal to 2 to the n
Since subsequences do not require continuity, you can sort the array first. If the interval [l, r] satisfies the condition nums[l] + nums[r] <= target, then all subsequences containing NUMs [l] satisfy the condition
Implementation:
function numSubseq(nums, target) {
// Can sort
nums.sort((a, b) = > a < b ? -1 : 1)
// Preprocessing computes the power table
const pow = [1]
for (let i = 1; i < nums.length; i++) {
pow[i] = (pow[i-1] < <1) % 1000000007
}
let count = 0
let left = 0
let right = nums.length - 1
while (left <= right) {
if (nums[left] + nums[right] > target) {
right--
} else {
// The combination number formula
count = (count + pow[right - left]) % 1000000007
left++
}
}
return count
}
Copy the codeLeetcode 3 – Medium
Answer:
Slide window + hash table records the first occurrence of the index position
Implementation:
function lengthOfLongestSubstring(s) {
if(! s) {return 0
}
const counter = {}
let result = 1
let left = 0
let right = 0
while (right < s.length) {
if(! (s[right]in counter)) {
// Record the first occurrence of the index position
counter[s[right]] = right
} else {
// Optimization point: On repetition, the left pointer moves to the next position where the index first appears
const oldLeft = left
left = counter[s[right]] + 1
// Delete counter data between old and new left
for (let i = oldLeft; i < left; i++) {
delete counter[s[i]]
}
counter[s[right]] = right
}
result = Math.max(result, right - left + 1)
right++
}
return result
}
Copy the codeLeetcode 239 – Difficult
Answer:
Fixed size window, the difficulty of this problem is: how to calculate the maximum window in O(1) time, in order to solve this problem, monotonous queue data structure is used
Implementation:
function maxSlidingWindow(nums, k) {
const queue = []
// Monotonic stack/queue template
// Maintain the first k number of monotonous queue: from the end of the queue to the head of the queue increment
for (let i = 0; i < k; i++) {
while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) {
queue.pop()
}
// Set index to index
queue.push(i)
}
const result = [nums[queue[0]]]
let right = k
while (right < nums.length) {
// Here we continue to maintain monotonic queues
// Use > also can AC, but the time is obviously increased, why? => queue.shilt() is called many times
while (queue.length && nums[right] >= nums[queue[queue.length - 1]]) {
queue.pop()
}
queue.push(right)
// The monotonic queue head (maximum index) is out of range
while (queue[0] <= right - k) {
queue.shift()
}
result.push(nums[queue[0]])
right++
}
return result
}
Copy the codeLeetcode 1438 – Medium
Answer:
The difficulty of this question is: how to calculate the maximum and minimum values of the window in O(1) time, similar to question 239
Implementation:
function longestSubarray(nums, limit) {
const queMin = []
const queMax = []
let left = 0
let right = 0
let result = 0
while (right < nums.length) {
while (queMax.length && nums[right] > queMax[queMax.length - 1]) {
queMax.pop()
}
queMax.push(nums[right])
while (queMin.length && nums[right] < queMin[queMin.length - 1]) {
queMin.pop()
}
queMin.push(nums[right])
// Based on question 239, we can get to this point
QueMax [0] can be used to obtain the maximum value of the interval, and queMin[0] can obtain the minimum value of the interval. If their absolute difference is illegal, the left interval needs to be shrunk
Nums [left] = queMax/queMin; nums[left] = queMax/queMin
while (queMax.length && queMin.length && queMax[0] - queMin[0] > limit) {
if (nums[left] === queMin[0]) {
queMin.shift()
}
if (nums[left] === queMax[0]) {
queMax.shift()
}
left++
}
result = Math.max(result, right - left + 1)
right++
}
return result
}
Copy the codeLeetcode 480 – Difficult
Answer:
This is a fairly classic sliding window problem, can be said to be very difficult. Enumerate the time complexity of the following solutions:
- The median of sorting calculation for every slide: the number of slides is
n-k, the time complexity of each sort isO(klogk), the total time complexity isO(nklogk) - Mean linear selection for each slide: the number of slides is
n-k, the time complexity of each median selection isO(k), the total time complexity isO(nk) - Double heap with “delete specified element” operation: the number of slides is
n-k, the heap size isO(k), the time complexity of deleting elements in the heap isO(k), the insertion time complexity isO(logk), the total time complexity isO(nk) - Double heap with lazy deleted elements: official solution, time complexity is
O(nlogn) - Bibalanced tree:
O(nlogk)The knowledge blind area is involved
The solution to this problem is: double heap with “delete specified element” operation. The idea of using double heap can refer to the median in leetcode-295 data stream
Implementation:
A heap with “delete specified element”, if Java, is the TAT with this data structure
// Heap data structure implementation with "delete specified element"
class Heap {
constructor(data = [], less) {
this.data = data
this.less = less || ((a, b) = > a < b)
if (this.length) {
for (let p = (this.length - 2) > >1; p >= 0; p--) {
this._down(p)
}
}
}
get length() {
return this.data.length
}
peak() {
return this.data[0]}remove(val) {
let index = -1
for (let i = 0; i < this.length; i++) {
if (this.data[i] === val) {
index = i
break}}if (index === -1) return false
this._swap(index, this.length - 1)
this.data.pop()
this._up(index)
this._down(index)
return true
}
push(val) {
this.data.push(val)
this._up(this.length - 1)}pop() {
if (!this.length) {
return
}
this._swap(0.this.length - 1)
const popItem = this.data.pop()
this._down(0)
return popItem
}
_swap(i, j){[this.data[i], this.data[j]] = [this.data[j], this.data[i]]
}
_up(i) {
if (i <= 0) return
const pIndex = (i - 1) > >1
if (this.less(this.data[i], this.data[pIndex])) {
this._swap(i, pIndex)
this._up(pIndex)
}
}
_down(i) {
let leftIndex = i * 2 + 1
if (leftIndex >= this.length) {
return
}
if (leftIndex + 1 < this.length && this.less(this.data[leftIndex+1].this.data[leftIndex])) {
leftIndex++
}
if (this.less(this.data[leftIndex], this.data[i])) {
this._swap(leftIndex, i)
this._down(leftIndex)
}
}
}
Copy the code295 questions, Median expansion in data streams:
// MedianFinder finds the median in the data stream
class MedianFinder {
constructor() {
// The maximum heap stores the smaller half of the input number
this.maxHeap = new Heap([], (a, b) = > a > b)
// The smallest heap stores the larger half of the input number
this.minHeap = new Heap([], (a, b) = > a < b)
}
push(num) {
if (!this.maxHeap.length || num <= this.maxHeap.peak()) {
this.maxHeap.push(num)
} else {
this.minHeap.push(num)
}
this.makeBalance()
}
remove(value) {
if (value <= this.maxHeap.peak()) {
this.maxHeap.remove(value)
} else {
this.minHeap.remove(value)
}
this.makeBalance()
}
findMedian() {
if (this.maxHeap.length === this.minHeap.length) {
return (this.maxHeap.peak() + this.minHeap.peak()) / 2
}
return this.maxHeap.peak()
}
// Adjust the balance of the two heaps
makeBalance() {
if (this.maxHeap.length > this.minHeap.length + 1) {
// The maximum heap is two more than the minimum heap, pop the maximum heap top, push into the minimum heap
this.minHeap.push(this.maxHeap.pop())
} else if (this.minHeap.length > this.maxHeap.length) {
// The minimum heap is larger than the maximum heap, pop the minimum heap top, push into the maximum heap
this.maxHeap.push(this.minHeap.pop())
}
}
}
Copy the codeFinally answer
// How to calculate the median of the interval, see 295
function medianSlidingWindow(nums, k) {
// Based on question 295, suppose we have a MedianFinder class that can help us find the median
const medianFinder = new MedianFinder()
for (let i = 0; i < k; i++) {
medianFinder.push(nums[i])
}
// Find the median of the first k digits
const result = [medianFinder.findMedian()]
// continue to iterate through the following
for (let i = k; i < nums.length; i++) {
// Remove the first one and add another one
medianFinder.remove(nums[i - k])
medianFinder.push(nums[i])
result.push(medianFinder.findMedian())
}
return result
}
Copy the codereference
Refer to some leetcode problem solutions
480 – Explain the time complexity of common solutions in this problem