记录算法笔记(2025.5.29)最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例 1:

输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]

输出： [null,null,null,null,-3,null,0,-2]

解释： MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); --> 返回 -3.

minStack.pop();

minStack.top(); --> 返回 0.

minStack.getMin(); --> 返回 -2.

提示：

• -231 <= val <= 231 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3 * 104 次

思路：可以搞两个栈，一个正常，一个从大到小排序的栈，栈顶为当前最小值，用空间换时间

代码：C#

public class MinStack {

     Stack<int> stack;

     Stack<int> minStack;

    public MinStack() {

        stack=new Stack<int>();

        minStack=new Stack<int>();

    }

   

    public void Push(int val) {

        stack.Push(val);

        if(minStack.Count==0 ||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();

    }

}