LeetCode 剑指 Offer 59 - II. 队列的最大值

Categories:

题目描述
思路分析
1. 解法一：单调队列（推荐）
相似题目

题目描述

✅ 剑指 Offer 59 - II. 队列的最大值

思路分析

解法一：单调队列（推荐）

核心思路：

维护普通队列保存所有元素。

维护一个单调递减队列保存可能的最大值。

入队时弹出所有小于新元素的值；出队时若等于队首则同步弹出。

复杂度分析：

时间复杂度：均摊 O(1)，每个元素最多进出队列各一次。

空间复杂度：O(n)。

import java.util.ArrayDeque;
import java.util.Deque;

class MaxQueue {
    private final Deque<Integer> data;
    private final Deque<Integer> max;

    public MaxQueue() {
        data = new ArrayDeque<>();
        max = new ArrayDeque<>();
    }

    public int max_value() {
        if (max.isEmpty()) {
            return -1;
        }
        return max.peekFirst();
    }

    public void push_back(int value) {
        data.addLast(value);
        while (!max.isEmpty() && max.peekLast() < value) {
            max.pollLast();
        }
        max.addLast(value);
    }

    public int pop_front() {
        if (data.isEmpty()) {
            return -1;
        }
        int val = data.pollFirst();
        if (!max.isEmpty() && max.peekFirst() == val) {
            max.pollFirst();
        }
        return val;
    }
}

type MaxQueue struct {
	data []int
	max  []int
}

func Constructor() MaxQueue {
	return MaxQueue{data: []int{}, max: []int{}}
}

func (q *MaxQueue) Max_value() int {
	if len(q.max) == 0 {
		return -1
	}
	return q.max[0]
}

func (q *MaxQueue) Push_back(value int) {
	q.data = append(q.data, value)

	for len(q.max) > 0 && q.max[len(q.max)-1] < value {
		q.max = q.max[:len(q.max)-1]
	}
	q.max = append(q.max, value)
}

func (q *MaxQueue) Pop_front() int {
	if len(q.data) == 0 {
		return -1
	}
	val := q.data[0]
	q.data = q.data[1:]

	if len(q.max) > 0 && q.max[0] == val {
		q.max = q.max[1:]
	}
	return val
}

相似题目

题目	难度	考察点
239. 滑动窗口最大值	困难	单调队列
862. 和至少为 K 的最短子数组	困难	单调队列
59 - II. 队列的最大值	中等	单调队列
346. 数据流中的移动平均值	简单	队列
933. 最近的请求次数	简单	队列
901. 股票价格跨度	中等	单调栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/90693853