LeetCode 716. 最大栈

Categories:

题目描述
思路分析
1. 解法一：双栈（推荐）
相似题目

题目描述

✅ 716. 最大栈

思路分析

解法一：双栈（推荐）

核心思路：

stack 保存元素，maxStack 保存当前最大值。

push/pop/top/peekMax 都是 O(1)。

popMax 通过缓冲栈移除栈顶最近的最大值。

复杂度分析：

时间复杂度：O(n)，其中 n 表示栈元素数量（popMax 最坏）。

空间复杂度：O(n)，需要辅助栈。

class MaxStack {
    private final Deque<Integer> stack = new ArrayDeque<>();
    private final Deque<Integer> maxStack = new ArrayDeque<>();

    public void push(int x) {
        stack.push(x);

        if (maxStack.isEmpty()) {
            maxStack.push(x);
        } else {
            maxStack.push(Math.max(x, maxStack.peek()));
        }
    }

    public int pop() {
        maxStack.pop();
        return stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return maxStack.peek();
    }

    public int popMax() {
        int max = maxStack.peek();
        Deque<Integer> buffer = new ArrayDeque<>();

        // 取出直到遇到最大值
        while (stack.peek() != max) {
            buffer.push(pop());
        }

        pop();

        // 把缓冲区元素放回
        while (!buffer.isEmpty()) {
            push(buffer.pop());
        }

        return max;
    }
}

type MaxStack struct {
    stack    []int
    maxStack []int
}

func Constructor() MaxStack {
    return MaxStack{
        stack:    make([]int, 0),
        maxStack: make([]int, 0),
    }
}

func (ms *MaxStack) Push(x int) {
    ms.stack = append(ms.stack, x)

    if len(ms.maxStack) == 0 {
        ms.maxStack = append(ms.maxStack, x)
    } else {
        curMax := ms.maxStack[len(ms.maxStack)-1]
        if x > curMax {
            curMax = x
        }
        ms.maxStack = append(ms.maxStack, curMax)
    }
}

func (ms *MaxStack) Pop() int {
    top := ms.stack[len(ms.stack)-1]
    ms.stack = ms.stack[:len(ms.stack)-1]
    ms.maxStack = ms.maxStack[:len(ms.maxStack)-1]
    return top
}

func (ms *MaxStack) Top() int {
    return ms.stack[len(ms.stack)-1]
}

func (ms *MaxStack) PeekMax() int {
    return ms.maxStack[len(ms.maxStack)-1]
}

func (ms *MaxStack) PopMax() int {
    maxVal := ms.PeekMax()
    buffer := make([]int, 0)

    // 取出直到遇到最大值
    for ms.Top() != maxVal {
        buffer = append(buffer, ms.Pop())
    }

    ms.Pop()

    // 把缓冲区元素放回
    for i := len(buffer) - 1; i >= 0; i-- {
        ms.Push(buffer[i])
    }

    return maxVal
}

相似题目

题目	难度	考察点
155. 最小栈	简单	栈
225. 用队列实现栈	简单	栈
232. 用栈实现队列	简单	栈
496. 下一个更大元素 I	简单	单调栈
739. 每日温度	中等	单调栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/29572000