题解 | 生成窗口最大值数组

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()
		num, _ := strconv.Atoi(scanner.Text())
		if num == 0 {
			break
		}
		scanner.Scan()
		w, _ := strconv.Atoi(scanner.Text())
		if num == 0 {
			break
		}
		arr := make([]int, num)
		for i := 0; i < num; i++ {
			scanner.Scan()
			arr[i], _ = strconv.Atoi(scanner.Text())
		}
		window := []int{}
		res := []int{}
		for i := 0; i < len(arr); i++ {
			// eg1 17/20
			// for len(window)>0 {
			//     if arr[i] > arr[window[len(window)-1]] {
			//         window = window[:len(window)-1]
			//     } else {
			//         break
			//     }
			// }

			// eg2 19/20
			l, r := 0, len(window)-1
			for l <= r {
				mid := (r-l)/2 + l
				if arr[window[mid]] < arr[i] {
					r = mid - 1
				} else {
					l = mid + 1
				}
			}
			if len(window) > 0 {
				window = window[:l]
			}

			window = append(window, i)
			if i-window[0] == w {
				window = window[1:]
			}

			if i >= w-1 {
				res = append(res, window[0])
			}
		}

		for i := 0; i < len(res); i++ {
			if i == len(res)-1 {
				fmt.Println(arr[res[i]])
			} else {
				fmt.Printf("%d ", arr[res[i]])
			}
		}
	}
}