func maxSlidingWindow(nums []int, k int) []int {
    q := NewMonotonicQueue()

    result := make([]int, 0, len(nums))

    for i := 0; i < k; i++ {
        q.Push(nums[i])
    }
    result = append(result, q.Max())

    for i := k; i < len(nums); i++ {
        q.Push(nums[i])
        q.Pop(nums[i-k])

        result = append(result, q.Max())
    }

    return result
}

type MonotonicQueue struct {
    l *list.List
}

func NewMonotonicQueue() *MonotonicQueue {
    return &MonotonicQueue {
        l: list.New(),
    }
}

func (q *MonotonicQueue) Push(x int) {
    for {
        back := q.l.Back()
        if back == nil || back.Value.(int) >= x {
            break
        }
        q.l.Remove(back)
    }

    q.l.PushBack(x)
}

func (q *MonotonicQueue) Pop(x int) {
    front := q.l.Front()
    if front.Value == x {
        q.l.Remove(front)
    }
}

func (q *MonotonicQueue) Max() int {
    return q.l.Front().Value.(int)
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func nextLargerNodes(head *ListNode) []int {
    values := toValues(head)
    
    n := len(values)
    result := make([]int, n)
    stack := make([]int, 0, n)

    for i := n-1; i >= 0; i-- {
        for len(stack) > 0 && stack[len(stack)-1] <= values[i] {
            stack = stack[:len(stack)-1]
        }

        if len(stack) > 0 {
            result[i] = stack[len(stack)-1]
        }
        stack = append(stack, values[i])
    }

    return result
}

func toValues(head *ListNode) []int {
    values := make([]int, 0, 1_0000)
    for head != nil {
        values = append(values, head.Val)
        head = head.Next
    }
    return values
}

func canSeePersonsCount(heights []int) []int {
    result := make([]int, len(heights))

    stack := make([]int, 0, len(heights))

    for i := len(heights) - 1; i >= 0; i-- {
        count := 0
        for len(stack) > 0 && stack[len(stack)-1] < heights[i] {
            stack = stack[:len(stack)-1]

            // 统计到「下一个等高或更高元素之间」有几个元素（已剔除被遮挡元素）
            count++
        }

        if len(stack) > 0 {
            result[i] = count + 1 // 也能看到「下一个等高或更高元素」
        } else {
            result[i] = count
        }
       
        stack = append(stack, heights[i]) 
    }

    return result
}

func finalPrices(prices []int) []int {
    n := len(prices)
    
    result := make([]int, n)
    stack := make([]int, 0, n)

    for i := n-1; i >= 0; i-- {
        // 找到下一个更小或相等元素
        for len(stack) > 0 && stack[len(stack)-1] > prices[i] {
            stack = stack[:len(stack)-1]
        }

        if len(stack) > 0 {
            result[i] = prices[i] - stack[len(stack)-1]
        } else {
            result[i] = prices[i]
        }

        stack = append(stack, prices[i])
    }

    return result
}

type StockSpanner struct {
    stack []Value
    day int
}

type Value struct {
    price int
    index int
}

func Constructor() StockSpanner {
    return StockSpanner{
        day: -1,
    }
}


func (this *StockSpanner) Next(price int) int {
    // 向前找 > 当前值的 index === 栈内剔除 <= 当前值的元素

    for len(this.stack) > 0 && this.stack[len(this.stack)-1].price <= price {
        this.stack = this.stack[:len(this.stack)-1]
    }

    this.day++

    var result int
    if len(this.stack) > 0 {
        lastDayIndex := this.stack[len(this.stack)-1].index
        result = this.day - lastDayIndex
    } else {
        result = this.day + 1
    }

    this.stack = append(this.stack, Value{price, this.day})

    return result
}


/**
 * Your StockSpanner object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Next(price);
 */

func removeKdigits(num string, k int) string {
    digits := []byte(num)
    n := len(digits)

    stack := make([]byte, 0, n)

    for _, digit := range digits {
        for k > 0 && len(stack) > 0 && stack[len(stack)-1] > digit {
            k--
            stack = stack[:len(stack)-1]
        }

        stack = append(stack, digit)
    }

    for k > 0 && len(stack) > 0 {
        k--
        stack = stack[:len(stack)-1]
    }

    return toString(stack)
}

func toString(digits []byte) string {
    for len(digits) > 0 && digits[0] == '0' {
        digits = digits[1:]
    }

    if len(digits) == 0 {
        return "0"
    }

    return string(digits)
}

func carFleet(target int, position []int, speed []int) int {
    cars := make([][]int, len(position))
    for i := range cars {
        cars[i] = []int{position[i], speed[i]}
    }
    slices.SortFunc(cars, func(a, b []int) int {
		return a[0] - b[0]
	})

    times := make([]float64, len(cars))
    for i, car := range cars {
        times[i] = float64(target-car[0]) / float64(car[1])
    }

    count := 0
    maxTimes := 0.0
    for i := len(times) - 1; i >= 0; i-- {
        if times[i] > maxTimes {
            count++
            maxTimes = times[i]
        }
    }

    return count
}