题解 | 最大值减去最小值小于或等于num的子数组数量

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	for {
		scanner := bufio.NewScanner(os.Stdin)

		// 设置大缓冲区，防止大输入时出错
		buf := make([]byte, 1024*1024) // 1MB
		scanner.Buffer(buf, 1024*1024)
		scanner.Split(bufio.ScanWords) // 按单词扫描（空格、换行等分隔）

		// 读取第一行：n
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())
		if n == 0 {
			break
		}
		scanner.Scan()
		num, _ := strconv.Atoi(scanner.Text())
		arr := make([]int, n)
		for i := 0; i < n; i++ {
			scanner.Scan()
			arr[i], _ = strconv.Atoi(scanner.Text())
		}
		fmt.Println(process(arr, num))
	}
}

// 单调栈思想，放置最大值，最小值
// 最大值所在的栈，单调递减
// 最小值所在的栈，单调递增
// 在left，right范围内求满足条件 arr[maxqueue[0]]-arr[minqueue[0]] < num
// right-left+1的值为子数组的长度
func process(arr []int, num int) int {
	maxqueue := []int{} // 单调递减
	minqueue := []int{} // 单调递增

	left := 0
	cnt := 0
	for right := 0; right < len(arr); right++ {
		for len(maxqueue) > 0 && arr[maxqueue[len(maxqueue)-1]] <= arr[right] {
			maxqueue = maxqueue[:len(maxqueue)-1]
		}
		maxqueue = append(maxqueue, right)

		for len(minqueue) > 0 && arr[minqueue[len(minqueue)-1]] >= arr[right] {
			minqueue = minqueue[:len(minqueue)-1]
		}
		minqueue = append(minqueue, right)

		for len(maxqueue) > 0 && len(minqueue) > 0 && arr[maxqueue[0]]-arr[minqueue[0]] > num {
			if maxqueue[0] == left {
				maxqueue = maxqueue[1:]
			}
			if minqueue[0] == left {
				minqueue = minqueue[1:]
			}
			left++
		}
		cnt += right - left + 1
	}
	return cnt
}