Week 16 @ 2025 算法周记【队列 + 单调栈】

1 队列
2 单调栈

队列

LC 641. Design Circular Deque 设计循环双端队列

https://leetcode.com/problems/design-circular-deque/description/

type MyCircularDeque struct {
    capacity int
    size int
    arr []int
    rear int
}


func Constructor(k int) MyCircularDeque {
    return MyCircularDeque {
        capacity: k,
        arr: make([]int, k),
        rear: -1,
    }
}


func (this *MyCircularDeque) InsertFront(value int) bool {
    if this.IsFull() {
        return false
    }

    if this.IsEmpty() {
        this.onlyOne(value)
        return true
    }

    newFront := this.index(this.frontIndex() + 1)
    this.arr[newFront] = value
    this.size++

    return true
}

func (this *MyCircularDeque) onlyOne(value int) {
    this.arr[0] = value
    this.rear = 0
    this.size = 1
}

func (this *MyCircularDeque) index(i int) int {
    if i < 0 {
        return i + this.capacity
    }
    if i >= this.capacity {
        return i - this.capacity
    }

    return i
}


func (this *MyCircularDeque) InsertLast(value int) bool {
    if this.IsFull() {
        return false
    }

    if this.IsEmpty() {
        this.onlyOne(value)
        return true
    }

    newRear := this.index(this.rear - 1)
    this.arr[newRear] = value
    this.rear = newRear
    this.size++

    return true
}

func (this *MyCircularDeque) frontIndex() int {
    return this.index(this.rear + this.size - 1)
}


func (this *MyCircularDeque) DeleteFront() bool {
    if this.IsEmpty() {
        return false
    }

    this.size--

    return true
}


func (this *MyCircularDeque) DeleteLast() bool {
    if this.IsEmpty() {
        return false
    }

    this.rear = this.index(this.rear + 1)
    this.size--

    return true
}


func (this *MyCircularDeque) GetFront() int {
    if this.IsEmpty() {
        return -1
    }

    return this.arr[this.frontIndex()]
}


func (this *MyCircularDeque) GetRear() int {
    if this.IsEmpty() {
        return -1
    }

    return this.arr[this.rear]
}


func (this *MyCircularDeque) IsEmpty() bool {
    return this.size == 0
}


func (this *MyCircularDeque) IsFull() bool {
    return this.size == this.capacity
}


/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * obj := Constructor(k);
 * param_1 := obj.InsertFront(value);
 * param_2 := obj.InsertLast(value);
 * param_3 := obj.DeleteFront();
 * param_4 := obj.DeleteLast();
 * param_5 := obj.GetFront();
 * param_6 := obj.GetRear();
 * param_7 := obj.IsEmpty();
 * param_8 := obj.IsFull();
 */

LC 1670. Design Front Middle Back Queue 设计前中后队列

https://leetcode.com/problems/design-front-middle-back-queue/description/

type FrontMiddleBackQueue struct {
    left *list.List
    right *list.List
}


func Constructor() FrontMiddleBackQueue {
    return FrontMiddleBackQueue {
        left:  list.New(),
		right: list.New(),
    }
}

// 始终维护「尽可能平衡」&「奇数时左边少右边多」
func (this *FrontMiddleBackQueue) balance() {
    // 维持「右边的数量 >= 左边的数量」
    for this.right.Len() < this.left.Len() {
        leftBack := this.left.Back()
        this.right.PushFront(leftBack.Value)
        this.left.Remove(leftBack)
    }
    // 位置「右边的数量 <= 左边的数量 + 1」
    for this.right.Len() > this.left.Len() + 1 {
        rightFront := this.right.Front()
        this.left.PushBack(rightFront.Value)
        this.right.Remove(rightFront)
    }
}


func (this *FrontMiddleBackQueue) PushFront(val int)  {
    this.left.PushFront(val)
    this.balance()
}


func (this *FrontMiddleBackQueue) PushMiddle(val int)  {
    this.left.PushBack(val)
    this.balance()
}


func (this *FrontMiddleBackQueue) PushBack(val int)  {
    this.right.PushBack(val)
    this.balance()
}


func (this *FrontMiddleBackQueue) PopFront() int {
    if this.left.Len() != 0 {
        front := this.left.Front()
        this.left.Remove(front)
        this.balance()
        return front.Value.(int)
    }

    if this.right.Len() != 0 {
        front := this.right.Front()
        this.right.Remove(front)
        this.balance()
        return front.Value.(int)
    }

    return -1
}


func (this *FrontMiddleBackQueue) PopMiddle() int {
    if this.right.Len() == 0 {
        return -1
    }

    if this.left.Len() < this.right.Len() {
        middle := this.right.Front()
        this.right.Remove(middle)
        this.balance()
        return middle.Value.(int)
    } else {
        middle := this.left.Back()
        this.left.Remove(middle)
        this.balance()
        return middle.Value.(int)
    }
}


func (this *FrontMiddleBackQueue) PopBack() int {
    if this.right.Len() == 0 {
        return -1
    }

    back := this.right.Back()
    this.right.Remove(back)
    this.balance()
    return back.Value.(int)

    return -1
}


/**
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.PushFront(val);
 * obj.PushMiddle(val);
 * obj.PushBack(val);
 * param_4 := obj.PopFront();
 * param_5 := obj.PopMiddle();
 * param_6 := obj.PopBack();
 */

LC 2073. Time Needed to Buy Tickets买票需要的时间

https://leetcode.com/problems/time-needed-to-buy-tickets/description/

 func timeRequiredToBuy(tickets []int, k int) int {
    // [0 ... i-1] [i] [i+1 ...]
    //    <tx>          <tx-1>

    total := 0

    tx := tickets[k]
    for i := 0; i <= k; i++ {
        total += min(tickets[i], tx)
    }
    for i := k+1; i < len(tickets); i++ {
        total += min(tickets[i], tx - 1)
    }

    return total
}

单调栈

模板：Calculate Next Greater Element

func calculateNextGreaterElement(nums []int) []int {
    result := make([]int, len(nums))
    ms := make([]int, 0, len(nums))

    for i := len(nums) - 1; i >= 0; i-- {
        for len(ms) > 0 && ms[len(ms)-1] <= nums[i] {
            ms = ms[:len(ms)-1]
        }

        if len(ms) == 0 {
            result[i] = -1
        } else {
            result[i] = ms[len(ms) - 1]
        }

        ms = append(ms, nums[i])
    }
    
    return result
}

LC 496. Next Greater Element I 下一个更大元素 I

https://leetcode.com/problems/next-greater-element-i/description/

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    nums2Map := make(map[int]int, len(nums2))
    for i, v := range nums2 {
        nums2Map[v] = i
    }

    next := calculateNextGreaterElement(nums2)

    result := make([]int, len(nums1))
    for i, v := range nums1 {
        result[i] = next[nums2Map[v]]
    }

    return result
}

func calculateNextGreaterElement(nums []int) []int {
    result := make([]int, len(nums))
    ms := make([]int, 0, len(nums))

    for i := len(nums) - 1; i >= 0; i-- {
        // 5 3 2 1
        for len(ms) > 0 && ms[len(ms)-1] <= nums[i] {
            ms = ms[:len(ms)-1]
        }

        if len(ms) == 0 {
            result[i] = -1
        } else {
            result[i] = ms[len(ms) - 1]
        }

        ms = append(ms, nums[i])
    }
    
    return result
}

LC 739. Daily Temperatures 每日温度

https://leetcode.com/problems/daily-temperatures/description/

func dailyTemperatures(temperatures []int) []int {
    result := make([]int, len(temperatures))
    ms := make([][]int, 0, len(temperatures))

    for i := len(temperatures) - 1; i >= 0; i-- {
        for len(ms) > 0 && ms[len(ms)-1][0] <= temperatures[i] {
            ms = ms[:len(ms)-1]
        }

        if len(ms) > 0 {
            d := ms[len(ms)-1][1]
            result[i] = d - i
        }

        ms = append(ms, []int{temperatures[i], i})
    }
    
    return result
}

LC 503. Next Greater Element II 下一个更大元素 II

https://leetcode.com/problems/next-greater-element-ii/description/

func nextGreaterElements(nums []int) []int {
    dupNums := append(nums, nums...)
    dupNext := calculateNextGreaterElement(dupNums)
    return dupNext[:len(nums)]
}

func calculateNextGreaterElement(nums []int) []int {
    result := make([]int, len(nums))
    ms := make([]int, 0, len(nums))

    for i := len(nums) - 1; i >= 0; i-- {
        // 5 3 2 1
        for len(ms) > 0 && ms[len(ms)-1] <= nums[i] {
            ms = ms[:len(ms)-1]
        }

        if len(ms) == 0 {
            result[i] = -1
        } else {
            result[i] = ms[len(ms) - 1]
        }

        ms = append(ms, nums[i])
    }
    
    return result
}

不实际构造翻倍数组

func nextGreaterElements(nums []int) []int {
    n := len(nums)

    result := make([]int, n)
    ms := make([]int, 0, n)

    for i := 2 * n - 1; i >= 0; i-- {
        ii := i % n

        for len(ms) > 0 && ms[len(ms)-1] <= nums[ii] {
            ms = ms[:len(ms)-1]
        }

        if len(ms) == 0 {
            result[ii] = -1
        } else {
            result[ii] = ms[len(ms) - 1]
        }

        ms = append(ms, nums[ii])
    }
    
    return result
}