单调栈

LC 581. Shortest Unsorted Continuous Subarray 最短无序连续子数组

​https://leetcode.com/problems/shortest-unsorted-continuous-subarray/description/

排序比较

func findUnsortedSubarray(nums []int) int {
    sorted := append([]int{}, nums...)
    sort.Ints(sorted)

    l := 0
    r := len(nums) - 1
    any := false

    for i := 0; i < len(nums); i++ {
        if nums[i] != sorted[i] {
            l = i
            any = true
            break
        }
    }
    for i := len(nums) - 1; i >= 0 ; i-- {
        if nums[i] != sorted[i] {
            r = i
            any = true
            break
        }
    }

    if !any {
        return 0
    }

    return r - l + 1
}

func findUnsortedSubarray(nums []int) int {
    sorted := append([]int{}, nums...)
    sort.Ints(sorted)

    l := -1
    r := -1

    for i := 0; i < len(nums); i++ {
        if nums[i] != sorted[i] {
            l = i
            break
        }
    }
    for i := len(nums) - 1; i >= 0 ; i-- {
        if nums[i] != sorted[i] {
            r = i
            break
        }
    }

    if l == -1 { // l r 只能同时为 -1 或同时不为 -1；-1 代表本就有序
        return 0
    }

    return r - l + 1
}

单调栈

func findUnsortedSubarray(nums []int) int {
    l := len(nums)
    stack := make([]int, 0, len(nums))
    for i := 0; i < len(nums); i++ {
        for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[i] {
            l = min(l, stack[len(stack)-1])
            stack = stack[:len(stack)-1]
        }

        stack = append(stack, i)
    }

    r := -1
    stack = make([]int, 0, len(nums))
    for i := len(nums) - 1; i >= 0 ; i-- {
        for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
            r = max(r, stack[len(stack)-1])
            stack = stack[:len(stack)-1]
        }

        stack = append(stack, i)
    }

    if r == -1 { // l r 只能同时为 -1 或同时不为 -1；-1 代表本就有序
        return 0
    }

    return r - l + 1
}

单调队列

实现可计算最大最小值的单调队列

type MonotonicQueue struct {
    q    []int
    maxq []int
    minq []int
}

func NewMonotonicQueue() *MonotonicQueue {
    return &MonotonicQueue{
        q:    []int{},
        maxq: []int{},
        minq: []int{},
    }
}

func (q *MonotonicQueue) Push(elem int) {
    q.q = append(q.q, elem)

    // maxq: 5 3 3 1
    for len(q.maxq) > 0 && q.maxq[len(q.maxq)-1] < elem {
        q.maxq = q.maxq[:len(q.maxq)-1]
    }
    q.maxq = append(q.maxq, elem)

    // minq: 1 3 3 5
    for len(q.minq) > 0 && q.minq[len(q.minq)-1] > elem {
        q.minq = q.minq[:len(q.minq)-1]
    }
    q.minq = append(q.minq, elem)
}

func (q *MonotonicQueue) Pop() int {
    elem := q.q[0]
    q.q = q.q[1:]

    if q.maxq[0] == elem {
        q.maxq = q.maxq[1:]
    }
    if q.minq[0] == elem {
        q.minq = q.minq[1:]
    }

    return elem
}

func (q *MonotonicQueue) Max() int {
    return q.maxq[0]
}

func (q *MonotonicQueue) Min() int {
    return q.minq[0]
}

func (q *MonotonicQueue) Size() int {
    return len(q.q)
}

func (q *MonotonicQueue) IsEmpty() bool {
    return len(q.q) == 0
}

LC 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit 绝对差不超过限制的最长连续子数组

​https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

func longestSubarray(nums []int, limit int) int {
    result := 0

    l, r := 0, 0
    q := NewMonotonicQueue()
    for r < len(nums) {
        q.Push(nums[r])

        for l < r && q.Max() - q.Min() > limit {
            q.Pop()
            l++
        }

        result = max(result, r - l + 1)
        r++
    }

    return result
}

type MonotonicQueue struct {
    q    []int
    maxq []int
    minq []int
}

func NewMonotonicQueue() *MonotonicQueue {
    return &MonotonicQueue{
        q:    []int{},
        maxq: []int{},
        minq: []int{},
    }
}

func (q *MonotonicQueue) Push(elem int) {
    q.q = append(q.q, elem)

    // maxq: 5 3 3 1
    for len(q.maxq) > 0 && q.maxq[len(q.maxq)-1] < elem {
        q.maxq = q.maxq[:len(q.maxq)-1]
    }
    q.maxq = append(q.maxq, elem)

    // minq: 1 3 3 5
    for len(q.minq) > 0 && q.minq[len(q.minq)-1] > elem {
        q.minq = q.minq[:len(q.minq)-1]
    }
    q.minq = append(q.minq, elem)
}

func (q *MonotonicQueue) Pop() int {
    elem := q.q[0]
    q.q = q.q[1:]

    if q.maxq[0] == elem {
        q.maxq = q.maxq[1:]
    }
    if q.minq[0] == elem {
        q.minq = q.minq[1:]
    }

    return elem
}

func (q *MonotonicQueue) Max() int {
    return q.maxq[0]
}

func (q *MonotonicQueue) Min() int {
    return q.minq[0]
}

func (q *MonotonicQueue) Size() int {
    return len(q.q)
}

func (q *MonotonicQueue) IsEmpty() bool {
    return len(q.q) == 0
}

两个 Heap 的解法

func longestSubarray(nums []int, limit int) int {
    result := 0

    h := &MinMaxHeap{}

    l, r := 0, 0
    
    for r < len(nums) {
        h.Push(nums[r], r)

        for l < r && h.Max() - h.Min() > limit {
            l = h.Pop()
        }

        result = max(result, r - l + 1)
        r++
    }

    return result
}

type MinMaxHeap struct {
    minh MinHeap
    maxh MinHeap
}

func (h *MinMaxHeap) Max() int {
    return -h.maxh[0][0]
}

func (h *MinMaxHeap) Min() int {
    return h.minh[0][0]
}

func (h *MinMaxHeap) Push(v int, index int) {
    heap.Push(&h.minh, []int{v, index})
    heap.Push(&h.maxh, []int{-v, index})
}

func (h *MinMaxHeap) Pop() int {
    newLeft := min(h.minh[0][1], h.maxh[0][1]) + 1

    for h.minh[0][1] < newLeft {
        heap.Pop(&h.minh)
    }
    for h.maxh[0][1] < newLeft {
        heap.Pop(&h.maxh)
    }

    return newLeft
}

type MinHeap [][]int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x any) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.([]int))
}

func (h *MinHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

LC 862. Shortest Subarray with Sum at Least K 和至少为 K 的最短子数组

​https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/description/

单调栈解法

func shortestSubarray(nums []int, k int) int {
    preSum := getPreSum(nums)
    q := NewMonotonicQueue()

    result := math.MaxInt

    l, r := 0, 0
    for r < len(preSum) {
        q.Push(preSum[r])
        r++
        

        for r < len(preSum) && !q.IsEmpty() && preSum[r] - q.Min() >= k {
            result = min(result, r-l)

            q.Pop()
            l++
        }
    }

    if result == math.MaxInt {
        return -1
    }

    return result
}

func getPreSum(nums []int) []int {
    preSum := make([]int, len(nums) + 1)
    for i := 0; i < len(nums); i++ {
        preSum[i+1] = preSum[i] + nums[i]
    }

    return preSum
}


type MonotonicQueue struct {
    q    []int
    maxq []int
    minq []int
}

func NewMonotonicQueue() *MonotonicQueue {
    return &MonotonicQueue{
        q:    []int{},
        maxq: []int{},
        minq: []int{},
    }
}

func (q *MonotonicQueue) Push(elem int) {
    q.q = append(q.q, elem)

    // maxq: 5 3 3 1
    for len(q.maxq) > 0 && q.maxq[len(q.maxq)-1] < elem {
        q.maxq = q.maxq[:len(q.maxq)-1]
    }
    q.maxq = append(q.maxq, elem)

    // minq: 1 3 3 5
    for len(q.minq) > 0 && q.minq[len(q.minq)-1] > elem {
        q.minq = q.minq[:len(q.minq)-1]
    }
    q.minq = append(q.minq, elem)
}

func (q *MonotonicQueue) Pop() int {
    elem := q.q[0]
    q.q = q.q[1:]

    if q.maxq[0] == elem {
        q.maxq = q.maxq[1:]
    }
    if q.minq[0] == elem {
        q.minq = q.minq[1:]
    }

    return elem
}

func (q *MonotonicQueue) Max() int {
    return q.maxq[0]
}

func (q *MonotonicQueue) Min() int {
    return q.minq[0]
}

func (q *MonotonicQueue) Size() int {
    return len(q.q)
}

func (q *MonotonicQueue) IsEmpty() bool {
    return len(q.q) == 0
}

堆解法

func shortestSubarray(nums []int, k int) int {
    result := math.MaxInt

    sum := 0
    h := Heap{}

    for i, num := range nums {
        sum += num

        if sum >= k {
            result = min(result, i+1)
        }

        for h.Len() > 0 && sum - h[0][0] >= k {
            result = min(result, i - h[0][1])
            heap.Pop(&h)
        }

        heap.Push(&h, []int{sum, i})
    }

    if result == math.MaxInt {
        return -1
    }

    return result
}

type Heap [][]int

func (h Heap) Len() int           { return len(h) }
func (h Heap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h Heap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *Heap) Push(x any) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.([]int))
}

func (h *Heap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}