LeetCode 面试题 03.02. 栈的最小值

Categories:

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

题目描述

✅ 面试题 03.02. 栈的最小值

思路分析

解法一：辅助栈（推荐）

核心思路：

维护两个栈：主栈存储所有元素，辅助栈（最小栈）同步维护当前的最小值

每次 push 时，若新元素 <= 辅助栈栈顶（或辅助栈为空），则同步压入辅助栈

每次 pop 时，若弹出元素等于辅助栈栈顶，则辅助栈也同步弹出

getMin 直接返回辅助栈栈顶，时间复杂度 O(1)

复杂度分析：

时间复杂度：O(1)，push、pop、getMin 均为常数时间

空间复杂度：O(n)，其中 n 为栈中元素数量，辅助栈最多存储 n 个元素

class MinStack {

    private Deque<Integer> stack;
    private Deque<Integer> minStack;

    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }

    public void push(int val) {
        stack.push(val);
        // 辅助栈为空或新值不大于当前最小值时同步压栈
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        int val = stack.pop();
        // 弹出值等于辅助栈栈顶时同步弹出
        if (val == minStack.peek()) {
            minStack.pop();
        }
    }

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

    public int getMin() {
        return minStack.peek();
    }
}

type MinStack struct {
    stack    []int
    minStack []int
}

func Constructor() MinStack {
    return MinStack{}
}

func (s *MinStack) Push(val int) {
    s.stack = append(s.stack, val)
    // 辅助栈为空或新值不大于当前最小值时同步压栈
    if len(s.minStack) == 0 || val <= s.minStack[len(s.minStack)-1] {
        s.minStack = append(s.minStack, val)
    }
}

func (s *MinStack) Pop() {
    top := s.stack[len(s.stack)-1]
    s.stack = s.stack[:len(s.stack)-1]
    // 弹出值等于辅助栈栈顶时同步弹出
    if top == s.minStack[len(s.minStack)-1] {
        s.minStack = s.minStack[:len(s.minStack)-1]
    }
}

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

func (s *MinStack) GetMin() int {
    return s.minStack[len(s.minStack)-1]
}

相似题目

题目	难度	考察点
155. 最小栈	中等	栈、辅助栈
716. 最大栈	困难	栈、设计
232. 用栈实现队列	简单	栈、设计
225. 用队列实现栈	简单	队列、设计
1381. 设计一个支持增量操作的栈	中等	栈、设计
剑指 Offer 30. 包含 min 函数的栈	简单	栈、辅助栈

本文作者: HGNULB

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