如何实现具备getMin功能的栈设计？

本文共计720个文字，预计阅读时间需要3分钟。

一、题目：实现一个特殊的栈，实现栈的基本功能并实现返回栈中最小元素的操作。

二、要求：

1.求1、pop、push、getMin操作的时空复杂度均为O(1)。

2.设计的栈类可以使用现有的栈结构。

3.分析实现过程。

三、分析：

1.使用两个栈，一个用于存储所有元素（栈S），另一个用于存储当前栈中最小元素（栈minS）。

2.当push元素时，如果该元素小于等于minS栈顶元素，则将其同时push到minS栈中。

3.当pop元素时，如果该元素等于minS栈顶元素，则将minS栈顶元素也pop出来。

4.当getMin操作时，直接返回minS栈顶元素。

具体实现如下：

python

class MinStack: def __init__(self): self.stack=[] # 存储所有元素 self.minStack=[] # 存储最小元素

def push(self, x: int) -> None: self.stack.append(x) if not self.minStack or x <=self.minStack[-1]: self.minStack.append(x)

def pop(self) -> None: if self.stack and self.minStack[-1]==self.stack[-1]: self.minStack.pop() self.stack.pop()

def top(self) -> int: return self.stack[-1]

def getMin(self) -> int: return self.minStack[-1]

一 题目

实现一个特殊的栈，实现栈的基本功能并实现返回栈中最小元素的操作。

二 要求

1、pop、push、getMin操作时间复杂度都是O（1）

2、设计的栈类型可以使用现成的栈结构

三 分析

我们可以使用两个栈，一个用来保存当前栈中的元素，其功能为正常的栈，记为stackData；另外一个用于保存每一步中的最小值，记为stackMin。

四 设计思路

4.1 压入规则

设当前数据为newNum，先将其压入stackData；

然后判断stackMin是否为空：

1.为空则将newNum压入stackMin中

2.不为空则比较newNum和stackMin栈顶元素哪一个更小

2.1如果newNum更小或者两者相等，则newNum也压入stackMin中；

2.2如果stackMin更小，则stackMin不压入任何内容；

4.2 弹出规则

1.先弹出stackMin栈顶元素，记为value

2.然后比较value和stackMin栈顶元素（记为min）的大小：

2.1 value == min，则stackMin弹出栈顶元素；

2.2否则stackMin不弹出任何内容。

4.3 查询栈中最小值操作

由压入和弹出规则可知，stackMin栈顶始终保存着stackData中最小的元素，所以只需要弹出栈顶元素即可。

五 代码实现

public class MyStack{ private Stack<Integer> stackData; private Stack<Integer> stackMin; public MyStack(){ this.stackData = new Stack<Integer>; this.stackMin = new Stack<Integer>; } public void push(int newNum){ if(this.stackMin.isEmpty()){ this.stackMin.push(newNum); }else if(newNum <= this.getMin()){ this.stackMin.push(newNum); } this.stackData.push(newNum); } public int pop(int newNum){ if(this.stackData.isEmpty()){ throw new RuntimeException("stackData is empty!"); } int value = this.stackData.pop(); if(value == this.getMin()){ this.stackMin.pop(); } return value; } public void getMin(){ if(this.stackMin.isEmpty()){ throw new RuntimeException("stackMin is empty!"); } return this.stackMin.pop(); } }