剑指Offer_编程题(C#实现)_包含min函数的栈

题目:包含min函数的栈

题目描述

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

解题思路

定义两个栈。一个存储栈,一个辅助栈。

Push方法:1. 存储栈 – 正常进栈即可。
2. 辅助栈 – 先定义一个数(目的是让第一个进栈的数进辅助栈),然后将这个数与之后进栈的数进行比较,当在这之后进栈的数小于这个数的时候,就把他存在辅助栈,若大于等于,则忽略,直接不执行。

Pop方法:1 . 存储栈 – 正常出栈即可。
2 . 辅助栈 – 如果存储栈出栈的这个数等于辅助栈将要出栈的数,那么辅助栈出栈,负责不搭理他,也不要出。

Top方法:只需 return dataStack.Peek(); 其中dataStack表示的是存储栈

Min方法:return minStack.Peek();其中dataStack表示的是辅助栈

注:Stack.Peek()和Stack.Pop()的相同点是 获取栈顶的值,不同点 则是 Stack.Peek()只是获取栈顶的值,而Stack.Pop()是获取栈顶的值然后删除。

参考代码

using System.Collections.Generic;
class Solution
{
    //定义两个栈,一个存储栈,一个辅助栈
    Stack<int> dataStack = new Stack<int>();
    Stack<int> minStack = new Stack<int>();
    int Min = int.MaxValue;
    public void push(int node) 
    {
        dataStack.Push(node);
        if(node<Min)
        {
            Min = node;
            minStack.Push(node);
        }
    }
    public void pop() 
    {
        int temp = dataStack.Pop();
        int mintemp = minStack.Peek();
        if(temp == mintemp)
            minStack.Pop();
    }
    public int top() 
    {
        return dataStack.Peek();
    }
    public int min() 
    {
        return minStack.Peek();
    }
}
上一篇:【剑指offer】包含min函数的栈


下一篇:集合系列 List(五):Stack