1 . 定义栈的数据结构;实现Push、Pop、Top、Min方法;时间复杂度为O(1) 。
思路:定义两个栈。一个存储栈,一个辅助栈。
Push方法:1. 存储栈 -- 正常进栈即可。
2. 辅助栈 -- 先定义一个数(随意,目的是让第一个进栈的数进辅助栈),然后将这个数与之后进栈的数进行比较,当在这之后进栈的数小于这个数的时候,就把他存在辅助栈,若大于等于,则忽略,直接不执行。
Pop方法:1 . 存储栈 -- 正常出栈即可。
2 . 辅助栈 -- 如果存储栈出栈的这个数等于辅助栈将要出栈的数,那么辅助栈出栈,负责不搭理他,也不要出。
Top方法:只需 return stack1.Peek(); 其中stack1表示的是存储栈,这里普及一下(Stack.peek()和Stack.pop()的相同点是 获取栈顶的值,不同点 则是 Stack.peek()只是获取栈顶的值,而Stack.pop()是获取栈顶的值然后删除。)
Min方法:在第二部Pop的时候来一手这个 Min = minstack2.Peek(); ,很稳,其中 minstack2表示的是辅助栈。
来,为了更好的理解,看图咯!!
using System.Collections.Generic;
//using泛型集合类List、DIctionary、Queue、Stack、SortedList,若不引用不可运行
class Solution
{
//定义两个栈,一个存储栈,一个辅助栈
Stack<int> stack1 = new Stack<int>();
Stack<int> minstack2 = new Stack<int>();
//先定义一个最小值Min,其中他的初始状态是int类型中的最大值(单纯的凑数而已,无关紧要)
int Min=int.MaxValue;
//push方法,首先是存储栈进栈,然后一个if函数,若进栈的这个数比辅助栈里面最小的数还小,则辅助栈也执行进栈
public void push(int node)
{
stack1.Push(node);
if(node<Min)
{
Min=node;
minstack2.Push(node);
}
}
//pop方法,若存储栈pop出的数等于最小值,辅助栈执行POP方法
public void pop()
{
if(stack1.Pop()== Min)
{
minstack2.Pop();
Min = minstack2.Peek();
}
}
//Stack.peek()和Stack.pop()的相同点是 获取栈顶的值,
//不同点 则是 Stack.peek()只是获取栈顶的值,而Stack.pop()是获取栈顶的值然后删除。
public int top()
{
return stack1.Peek();
}
//不解释
public int min()
{
return Min;
}
}