golang刷leetcode技巧之如何实现队列的最大值

问题描述

题目要求实现一个队列数据结构，其中包含以下三个操作：

1. void push_back(int value)：将元素 value 插入队尾。
2. int pop_front()：删除队头元素并返回该元素的值。
3. int max_value()：返回队列中的最大值。

解决思路

为了实现获取队列中的最大值，我们需要每次在插入或删除元素时更新最大值。使用一个辅助的双向队列（deque）来记录当前队列中的最大值。

具体实现

1. 定义一个双向队列 maxQueue 用于保存当前队列中的最大值。
2. 入队操作 push_back(value)：首先将元素 value 插入队尾。然后从队尾开始，删除小于 value 的元素，保证队列中的元素始终按照非递增顺序排列。最后将 value 插入队尾。
3. 出队操作 pop_front()：如果队头元素等于 maxQueue 的队头元素，则需要将 maxQueue 的队头元素同时删除。然后再删除队头元素并返回。
4. 获取最大值操作 max_value()：直接返回 maxQueue 的队头元素。

package main

import (
	"fmt"
	"container/list"
)

type MaxQueue struct {
	queue *list.List
	maxQ  *list.List
}

func Constructor() MaxQueue {
	return MaxQueue{
		queue: list.New(),
		maxQ:  list.New(),
	}
}

func (mq *MaxQueue) Max_value() int {
	if mq.maxQ.Len() == 0 {
		return -1
	}
	return mq.maxQ.Front().Value.(int)
}

func (mq *MaxQueue) Push_back(value int) {
	mq.queue.PushBack(value)
	for mq.maxQ.Len() > 0 && mq.maxQ.Back().Value.(int) < value {
		mq.maxQ.Remove(mq.maxQ.Back())
	}
	mq.maxQ.PushBack(value)
}

func (mq *MaxQueue) Pop_front() int {
	if mq.queue.Len() == 0 {
		return -1
	}
	val := mq.queue.Front().Value.(int)
	if mq.maxQ.Front().Value.(int) == val {
		mq.maxQ.Remove(mq.maxQ.Front())
	}
	mq.queue.Remove(mq.queue.Front())
	return val
}

func main() {
	queue := Constructor()
	queue.Push_back(1)
	queue.Push_back(3)
	queue.Push_back(2)
	queue.Push_back(5)
	fmt.Println(queue.Max_value()) // 输出：5
	fmt.Println(queue.Pop_front()) // 输出：1
	fmt.Println(queue.Max_value()) // 输出：5
}

以上就是使用双向队列实现队列最大值的相关代码和思路。通过维护一个辅助的双向队列来实现获取队列中的最大值。每次插入或删除元素时，都更新辅助队列来保证其非递增的有序性。这样可以在 O(1) 的时间复杂度内获取队列中的最大值。