LeetCode 剑指 Offer 30. 包含min函数的栈

Categories:

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

题目描述

✅ 剑指 Offer 30. 包含min函数的栈

思路分析

解法一：辅助最小栈（推荐）

核心思路：

主栈保存正常元素。

辅助栈保存当前最小值，当压入元素小于等于最小值时同步入栈。

弹栈时若弹出元素等于当前最小值，同步弹出辅助栈。

复杂度分析：

时间复杂度：O(1)，每个操作均为常数时间。

空间复杂度：O(n)，辅助栈最多保存 n 个元素。

class MinStack {
    private final Deque<Integer> data;
    private final Deque<Integer> mins;

    public MinStack() {
        data = new ArrayDeque<>();
        mins = new ArrayDeque<>();
    }

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

        if (mins.isEmpty() || x <= mins.peek()) {
            mins.push(x);
        }
    }

    public void pop() {
        int val = data.pop();
        if (val == mins.peek()) {
            mins.pop();
        }
    }

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

    public int min() {
        return mins.peek();
    }
}

type MinStack struct {
	data []int
	mins []int
}

func Constructor() MinStack {
	return MinStack{
		data: make([]int, 0),
		mins: make([]int, 0),
	}
}

func (s *MinStack) Push(x int) {
	s.data = append(s.data, x)

	if len(s.mins) == 0 || x <= s.mins[len(s.mins)-1] {
		s.mins = append(s.mins, x)
	}
}

func (s *MinStack) Pop() {
	n := len(s.data)
	val := s.data[n-1]
	s.data = s.data[:n-1]

	if val == s.mins[len(s.mins)-1] {
		s.mins = s.mins[:len(s.mins)-1]
	}
}

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

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

相似题目

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

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/42894963