2021-02-28: Given an integer array arr and an integer num. Subarray sub in an ARR must satisfy the following criteria: maximum value of sub – minimum value of sub < = nu

2021-02-28: Given an integer array arr and an integer num. Subarray sub in arR <= num (subarray sub in arR) <= num (subarray sub in arR)

Answer 2021-02-28:

Two double-ended queues are used to store serial numbers. MaxWindow goes from large to small, minWindow goes from small to large. 1. Right expansion of two dual-end queues at the same time. When the Max – min value is greater than sum, the loop exits. 2. Count. 3. Delete the expiration number on the left of the dual-end queue. With the code.

The code is written in Golang, and the code is as follows:

package main

import (
    "container/list"
    "fmt"
)

func main(a) {
    arr := []int{1.2}
    sum := 6
    ret := num(arr, sum)
    fmt.Println(ret)

}

func num(arr []int, sum int) int {
    arrLen := len(arr)
    if arrLen == 0 || sum < 0 {
        return 0
    }
    count := 0
    maxWindow := list.New().Init()
    minWindow := list.New().Init()
    R := 0
    for L := 0; L < arrLen; L++ {
        for R < arrLen {
            / / right expansion
            for maxWindow.Len() > 0 && arr[maxWindow.Back().Value.(int)] <= arr[R] {
                maxWindow.Remove(maxWindow.Back())
            }
            maxWindow.PushBack(R)
            / / right expansion
            for minWindow.Len() > 0 && arr[minWindow.Back().Value.(int)] >= arr[R] {
                minWindow.Remove(minWindow.Back())
            }
            minWindow.PushBack(R)

            // If Max - min >sum, no right expansion.
            if arr[maxWindow.Front().Value.(int)]-arr[minWindow.Front().Value.(int)] > sum {
                break
            } else {
                R++
            }

        }
        / / count
        count += R - L
        // Delete expired window data
        if maxWindow.Front().Value.(int) == L {
            maxWindow.Remove(maxWindow.Front())
        }
        if minWindow.Front().Value.(int) == L {
            minWindow.Remove(minWindow.Front())
        }
    }
    return count
}
Copy the code

The result is as follows:

Left God Java code reviews