【基本数据结构】变形题：最小栈的最优解

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

这是我在面试遇到的问题，大家可以想一想，如何实现时间和空间都是 O(1)，核心突破口在于数值范围，有一定难度。
问题描述：
实现一个这样的栈，这个栈除了可以进行普通的push、pop操作以外，还可以进行getMin的操作，getMin方法被调用后，会返回当前栈的最小值。栈里面存放的都是 int 整数，并且数值的范围是 [-100000, 100000]。要求所有操作的时间复杂度是 O(1)。

附加：如果空间复杂度也能O(1)的话可加分

要求：时间+空间都是O（1）就当作选做吧，你可以说一说你的想法，让空间/尽可能小勒。
答案：明天给答案吧

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

答案已经出来了，大家看这个文章解析：Shopee面试：最小栈的最优解

shuaidi

更新于 3 年前 294 30

共以下 28 个回答

神经蛙普通 2023年7月16日上午11:48

/**
    时间复杂度O(1)
    空间复杂度O(1)
    有范围限制
*/
class MinStack {

    LinkedList<Integer> stack;
    int min;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new LinkedList<>();
    }

    public void push(int x) {
        if (stack.isEmpty()) {
            stack.add(0);
            min = x;
        } else {
        // 将x和当前最小值的差值入栈
        // 若是负数，则表示x是最小值
        // 若是正数，则表示min还是最小值
        stack.add(x - min);
        // 判断最小值
        min = Math.min(min, x);  
        }

    }

    public void pop() {
        int tmp = stack.removeLast();
        // 若出栈值小于0，则最小值变化，要更新最小值
        // newMin = x
        // x - (x - oldMin)
        if (tmp < 0) {
            min = min - tmp;
        }
    }

    public int top() {
        return stack.getLast() < 0 ? min : stack.getLast() + min;
    }

    public int min() {
        return min;
    }
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月15日下午5:25

直接实现min函数的方式与剑指offer 30 一样，使用两个栈的方式来实现，时间复杂度为O（n）。
下面是代码

public class MinStack {
    private Stack<Integer> stack = new Stack<Integer>();
    private int minVal;

    public void push(int x) {
        if (stack.isEmpty()) {
            minVal = x;
            stack.push(0);
        } else {
            int compare = x - minVal;
            stack.push(compare);
            minVal = compare < 0 ? x : minVal;
        }
    }

    public void pop() {
        int top = stack.peek();
        minVal = top < 0 ? (minVal - top) : minVal;
        stack.pop();
    }

    public int top() {
        int top = stack.peek();
        return top < 0 ? minVal : (top + minVal);
    }

    public int min() {
        return minVal;
    }
}

增加了一个pop()函数，可以实现剑指的第30题，但是剑指的val值应该是-231 <= val <= 231 – 1，所以最终无法通过所有测试用例。测试用例实现18/19.

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月14日下午11:09

public class 设计一个有gitMin的栈 {

    private Stack<Integer> stack = new Stack<Integer>();
    private int min;

    public void push(int x) {
        if (stack.isEmpty()) {
            min = x;
            stack.push(0);
        } else {
            // 计算差值
            int compare = x - min;
            stack.push(compare);
            // 如果差值小于0，显然 x 成为最小值，否则最小值不变
            min = compare < 0 ? x : min;
        }
    }

    public void pop() {
        int top = stack.peek();
        // 如果top小于0，显然最小值也一并会被删除，此时更新最小值
        min = top < 0 ? (min - top) : min;
        stack.pop();
    }

    public int getMin() {
        return min;
    }
 }

0 赞同 0 条回复

Mby 普通 2023年7月14日下午7:04

public class {//设计一个由gitMin的栈

    private Stack<Integer> stack = new Stack<Integer>();
    private int min;

    public void push(int x){
        if(stack.isEmpty()){
            min = x;
            stack.push(0);
        }else{
            //计算差值
        int flag = x - min;
        stack.push(flag);
        //如过差值小于0，显然x成为最小值，否则最小值不变
        min = flag < 0 ? x : min;
        }
        }
        public void pop(){
        int top = stack.peek();
        //如果top小于0，显然最小值也一并会被删除，此时更新最小值
        min = top < 0 ? (min - top) : min;
        stack.pop();
        }

        public int gteMin(){
        return min;
        }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月14日下午3:53

已学习

0 赞同 0 条回复

登录以回复

Marshan 普通 2023年7月14日下午3:06

// 实现一个这样的栈，这个栈除了可以进行普通的push、pop操作以外，还可以进行getMin的操作，getMin方法被调用后，会返回当前栈的最小值。栈里面存放的都是 int 整数，并且数值的范围是 [-100000, 100000]。要求所有操作的时间复杂度是 O(1)。
// 附加：如果空间复杂度也能O(1)的话可加分。
// 我们的 stack 栈中，不能存放原始数值，而是应该存放 差值，啥差值？就是存放栈顶与最小值的差值。

#include<iostream>
#include<stack>

using namespace std;

class Stack{
    private:
        stack<int> stack;
        int min;

    public:
        void push(int x){
            if(stack.empty()){
                stack.push(0);
                min = x;
            }
            else{
                int compare = x - min;
                stack.push(compare);
                min = compare<0?x:min;
            }
        }

        void pop(){
            int top = stack.top();
            min = top<0?(min - top):min;
            stack.pop();
        }

        int getMin(){
            return min;
        }
};
int main(){

}

0 赞同 0 条回复

枫梓。普通 2023年7月14日下午1:07

打卡同第一题

0 赞同 0 条回复

登录以回复

片言莫语普通 2023年7月14日下午12:02

public class 设计一个有gitMin的栈 {

    private Stack<Integer> stack = new Stack<Integer>();
    private int min;

    public void push(int x) {
        if (stack.isEmpty()) {
            min = x;
            stack.push(0);
        } else {
            // 计算差值
            int compare = x - min;
            stack.push(compare);
            // 如果差值小于0，显然 x 成为最小值，否则最小值不变
            min = compare < 0 ? x : min;
        }
    }

    public void pop() {
        int top = stack.peek();
        // 如果top小于0，显然最小值也一并会被删除，此时更新最小值
        min = top < 0 ? (min - top) : min;
        stack.pop();
    }

    public int getMin() {
        return min;
    }
 }

0 赞同 0 条回复

Fighting boy😀 普通 2023年7月13日下午11:00

class MinStack {
public:
stack s;
int min;
MinStack() {

}

void push(int val) {
if(s.empty())
{
min=val;
s.push(0);
}else
{
int t=val-min;// 可能会发生溢出
if(t<0)
{
min=val;
}
s.push(t);
}
}

void pop() {
int k=s.top();
if(k<0)
{
min=min-k;
}
s.pop();
}

int top() {
return s.top() < 0 ? min : s.top() + min;
}

int getMin() {
return min;
}
};

0 赞同 0 条回复

登录以回复
艺普通 2023年7月13日下午10:51
“`c++
class MinStack {
public:
stack s;
int min;
MinStack() {
```
}

void push(int val) {
```
if(s.empty())
{
min=val;
s.push(0);
}else
{
int t=val-min;// 可能会发生溢出
if(t<0)
{
min=val;
}
s.push(t);
}
}
```
void pop() {
```
int k=s.top();
if(k<0)
{
min=min-k;
}
s.pop();
}
```
int top() {
```
return s.top() < 0 ? min : s.top() + min;
}
```
int getMin() {
```
return min;
}
};

“`
0 赞同 0 条回复

登录以回复

NullPointerException 普通 2023年7月13日下午9:45

// 存储差值差值 = 入值 – min 如果大于0 那么 min 不变如果 <0 min 肯定要更新成新入值
Stack stack;
int min =0;
/** initialize your data structure here. */
public MinStack() {
stack =new Stack();
}

public void push(int x) {
    if(stack.isEmpty())
    {
     min = x;
     stack.push(0);
    }else
    {
        int cha = x- min;
        if(cha<0)
        {
            min  = x;
        }
        stack.push(cha);
    }
}

public void pop() {
    int cha = stack.pop();
    if(cha<0)
    {
        //差值<0 代表小元素离开栈顶 要根据差值计算新的min
        // cha = x -原min   对于 cha<0  新min=x
        // cha= 新min -原min  原min=新min-cha
        min = min -cha ;
    }
}

public int top() {
        int cha = stack.peek();
    if(cha<0)
    {
        //差值<0 代表小元素离开栈顶 要根据差值计算新的min
        // cha = x -原min   对于 cha<0  新min=x
        // cha= 新min -原min  原min=新min-cha
       return min;
    }else{ return  cha+min ;}
}

public int min() {
    return min ;
}

}

0 赞同 0 条回复

北辰普通 2023年7月13日下午7:38

public class 设计一个有getMin的栈 {
    public Stack<Integer> stack = new Stack<>();
    public int min;//存储最小值

    public void push(int x) {
        if(stack.isEmpty()) {
            stack.push(0);
            min = x;
        }else {
            stack.push(x-min);
            min = x-min<0?x:min;
        }
    }

    public void pop() {
        int top = stack.pop();
        min = top<0?min-top:min;
    }

    public int getMin() {
        return min;
    }

    public static void main(String[] args) {

    }
}

0 赞同 0 条回复

#00456B 普通 2023年7月13日下午4:56

使用差值法，用stack来记录差值，但是在lc中需要改为long，否则会溢出

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stk_diff;
    int minNum;
    MinStack() {

    }

    void push(int x) {
        if(stk_diff.empty()){
            minNum = x;
            stk_diff.push(0);
        }
        else{
            stk_diff.push(x-minNum);
            minNum = std::min(x,minNum);
        }
    }

    void pop() {
        if(stk_diff.top() <= 0){
            minNum -= stk_diff.top();
        }
        stk_diff.pop();
    }

    int top() {
        if(stk_diff.top() >= 0){
            return stk_diff.top() + minNum;
        }
        else{
            return minNum;
        }
    }

    int min() {
        return minNum;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */

0 赞同 0 条回复

momo 普通 2023年7月13日下午2:48

最小栈的最优解

class MinStack {
    Deque<Integer> stack;
    int min;

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

    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(0);
            min = x;
        } else {
            stack.push(x - min);
            min = Math.min(min, x);
        }
    }

    public void pop() {
        if (stack.peek() < 0) {
            min = min - stack.peek();
        }
        stack.pop();
    }

    public int top() {
        if (stack.peek() < 0) {
            return min;
        } else {
            return stack.peek() + min;
        }
    }

    public int min() {
        return min;
    }
}

0 赞同 0 条回复

CaCO3 永久会员 2023年7月12日下午9:25

”’java

public class Solution{
private Stack stack = new Stack<>();
private int min;
public void push(int x){
if(stack.isEmpty()){
min = x;
stack.push(0);
}else{
//计算差值
int compare = x – min;
stack.push(compare);
//如果差值小于0，则x为最小值，否则最小值不变
min = compare < 0 ? x: min;
}
}
public void pop(){
int top = stack.peek();
//top小于0，最小值也会被删除
min = top < 0 ? (min-top):min;
stack.pop();
}
public int getMin(){
return min;
}

}
”’

0 赞同 0 条回复

登录以回复

人生何处不青山普通 2023年7月12日下午5:53

用插值法

class MinStack {
    private stack: number[]
    private minVal: number
    constructor() {
        this.stack = [];
        this.minVal = 0;
    }

    push(x: number): void {
        if (this.stack.length === 0) {
            this.stack.push(0);
            this.minVal = x;
        } else {
            let t = x - this.minVal;
            this.stack.push(t);
            this.minVal = t < 0 ? x : this.minVal;
        }
    }

    pop(): void {
        let lastVal = this.stack[this.stack.length - 1];
        this.minVal = lastVal < 0 ? this.minVal - lastVal : this.minVal;
        this.stack.pop();
    }

    top(): number {
        let lastVal = this.stack.slice(-1)[0];
        return lastVal < 0 ? this.minVal : this.minVal + lastVal;
    }

    min(): number {
        return this.minVal;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.min()
 */

0 赞同 0 条回复

AD钙奶普通 2023年7月12日下午3:53

在前面那道题贴过一次了，原来还有一个打卡。那就再贴一次，具体思路写在前面那题的打卡里了。
有点区别的是，这题规定了数据范围，int是够的，而LC那道会超范围，所以用了long，其它都差不多。

class MinStack {
    Deque deque = new ArrayDeque<>();
    long mn;
    /** initialize your data structure here. */
    public MinStack() {

    }
    
    public void push(int x) {
        if(deque.isEmpty()) {
            mn = x;
            deque.addFirst(0L);
        } else {
            deque.addFirst(x - mn);
            mn = Math.min(mn,x);
        }

    }
    
    public void pop() {
        if(deque.isEmpty()) return;
        long temp = deque.removeFirst();
        if(temp < 0) {
            mn -= temp; 
        }
    }
    
    public int top() {
        long temp = deque.peekFirst();
        if(temp < 0) return (int)mn;
        return (int)(temp + mn);
    }
    
    public int min() {
        return (int)mn;
    }
}

0 赞同 0 条回复

Mooby 普通 2023年7月12日下午3:43

五

0 赞同 2 条回复

登录以回复
- shuaidi 永久会员 @ Mooby 2023年7月13日下午12:18
  
  你都刷过的了，重复参加了哦
  
  登录以回复
- Mooby 普通 @ shuaidi 2023年7月13日下午1:31
  
  再刷一次嘿嘿
  
  登录以回复

doordie. 普通 2023年7月12日上午9:49

采用辅助变量来保证时间复杂度和空间复杂度都是O(1)

public class MinStack2 {
    Stack<Integer> stack;
    int min;

    public MinStack2(){
        stack = new Stack<Integer>();
    }
    // 入栈
    public void push(int x){
        if (stack.isEmpty()){
            stack.push(0);
            min = x;
        }else {
            // 入栈 差值
            stack.push(x-min);
            // 存最小值
            min = Math.min(min,x);
        }
    }
    public void pop() {
        // 若栈顶元素<0 说明是最小值
        if (stack.peek() < 0) {
            // 最小值更新  得到上一个最小值
            min = min - stack.peek();
        }
        stack.pop();
    }

    public int top() {
        if (stack.peek() < 0){
            return (int) min;
        }

        else{
            return (int) (stack.peek() + min);
        }
    }

    public int min() {
        return (int) min;
    }
}

0 赞同 0 条回复

普通 2023年7月11日下午11:52

感觉这题和那个维护最小栈是把原来的空间O(N),通过差值变换成O(1)
下面是代码在第一题的提交上数值越界了，按理说数值有取值限制的话应该能过
class MinStack {
public:
/** initialize your data structure here. */
stack stack1;
stack stack2;//栈顶元素维护最小值
int minx=2147483647;
MinStack() {

}

void push(int x) 
{
    if(stack1.empty())
    {
        stack1.push(0);
        minx=x;
    }
    else
    {
        stack1.push(x-minx);
        if(x<=minx)
          minx=x;
    }
}

void pop() 
{
    if(stack1.top()<0)
    {
        minx-=stack1.top();
         stack1.pop();
    }
      else
      {
     stack1.pop();
      }


}

int top() {

    return stack1.top()+minx;
}

int min() 
{
    return minx;
}

};

0 赞同 0 条回复

wonderful 普通 2023年7月11日下午11:25

class MinStack:
def init(self):
# 元素栈
self.stack = []
# 辅助栈
self.min_stack = []

def push(self, x):
    # 有元素入栈时，
    # 该元素与辅助栈的栈顶的代表最小值的元素进行比较
    # 把最小值压入辅助栈
    self.stack.append(x)
    if len(self.min_stack) > 0:
        self.min_stack.append(min(x, self.min_stack[-1]))
    else:
        self.min_stack.append(x)

def pop(self):
    # 有元素出栈时，辅助栈内的元素也一并出栈
    self.stack.pop()
    self.min_stack.pop()

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

def min(self):
    # 任何时刻， 栈内最小元素就是辅助栈的栈顶元素
    return self.min_stack[-1]

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月11日下午10:49

代码

public class MinStack {

    private Stack<Integer> stack = new Stack<Integer>();
    private int min;

    public void push(int x) {
        if (stack.isEmpty()) {
            min = x;
            stack.push(0);
        } else {
            // 计算差值
            int compare = x - min;
            stack.push(compare);
            // 如果差值小于0，显然 x 成为最小值，否则最小值不变
            min = compare < 0 ? x : min;
        }
    }

    public void pop() {
        int top = stack.peek();
        // 如果top小于0，显然最小值也一并会被删除，此时更新最小值
        min = top < 0 ? (min - top) : min;
        stack.pop();
    }

    public int getMin() {
        return min;
    }
 }

0 赞同 0 条回复

Luminous 普通 2023年7月11日下午10:33

class MinStack {

    private List<Integer> stack;
    private int min;
    /** initialize your data structure here. */
    public MinStack() {
        stack=new ArrayList<Integer>();
    }

    public void push(int x) {
        //只将差值压入栈
        if(stack.isEmpty()){
            min=x;
            stack.add(0);
        }else{
            int compare=x-min;
            min=compare<0?x:min;
            stack.set(0,compare);
        }
    }

    public void pop() {
        //如果栈顶小于0的话，说明栈顶就是最小值，需更新最小值
        int top=stack.get(0);
        min=top<0?min-top:min;
        stack.remove(0);
    }
    public int min() {
        return min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

0 赞同 0 条回复

CKX 普通 2023年7月11日下午10:01

type MinStack struct {
    //栈中记录差值
    stack []int
    min int
}


/** initialize your data structure here. */
func Constructor() MinStack {
    return MinStack{}
}


func (this *MinStack) Push(x int)  {
    if len(this.stack) == 0 {
        this.min = x
        this.stack = append(this.stack, 0)
    } else {
        //计算差值
        compare := x - this.min
        this.stack = append(this.stack, compare)
        if x < this.min {
            this.min = x
        }
    }
}


func (this *MinStack) Pop()  {
    if len(this.stack) > 0 {
        temp := this.stack[len(this.stack) - 1]
        this.stack = this.stack[:len(this.stack)-1]
        //如果top小于0,栈顶值与最小值相等
        //更新最小值
        if temp < 0 {
            this.min = this.min - temp
        }
    }
}


func (this *MinStack) Top() int {
    if len(this.stack) == 0 {
        return -1
    }
    temp := this.stack[len(this.stack) - 1]
    if temp > 0 {
        return temp + this.min
    } else {
        return this.min
    }
}


func (this *MinStack) Min() int {
    return this.min
}

0 赞同 0 条回复

阿尚普通 2023年7月11日下午8:23

//一个栈实现
class MinStack {
    Stack<Integer> stack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int x) {
        if(stack.isEmpty() || x < stack.peek()){
            stack.push(x);
            stack.push(x);
        }else{
            int minVal = stack.peek();
            stack.push(x);
            stack.push(minVal);
        }
    }

    public void pop() {
        if(stack.isEmpty()) return;
        stack.pop();
        stack.pop();
    }

    public int top() {
        int minVal = stack.pop();
        int topVal = stack.peek();
        stack.push(minVal);
        return topVal;
    }

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

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

0 赞同 0 条回复

V2ero 普通 2023年7月11日下午7:22

妙啊

class Stack {
    private arr: number[];

    constructor() {
        this.arr = [];
    }

    push(x: number) {
        this.arr.push(x);
    }

    pop() {
        return this.arr.pop();
    }

    top() {
        return this.arr[this.arr.length - 1];
    }

    isEmpty() {
        return !!!this.arr.length;
    }
}

/**
 * 辅助栈
 */
class MinStack {
    min: number;
    stack: Stack;
    constructor() {
        this.stack = new Stack();
        this.min = Infinity;
    }

    push(x: number): void {
        if (this.stack.isEmpty()) {
            this.min = x;
            this.stack.push(0);
        } else {
            const compare = x - this.min;
            this.stack.push(compare);
            this.min = compare < 0 ? x : this.min;
        }
    }

    pop(): void {
        const top = this.stack.top();
        this.min = top < 0 ? this.min - top : this.min;
        this.stack.pop();
    }

    getMin(): number {
        return this.min;
    }
}

0 赞同 0 条回复

波雅汉库克普通 2023年7月11日下午4:59

class MinStack {
public:
    long minNum;
    stack<long> stk;

    MinStack() {}

    void push(int val) {
        if(stk.empty()){
            minNum = (long)val;
            stk.push(0);

            return;
        }
        long dif = (long)val - minNum;
        stk.push(dif);
        minNum = dif >= 0? minNum: val;

    }

    void pop() {
        long top = stk.top();
        if(top < 0){
            //cur is the min
            minNum = minNum - top;
        }
        stk.pop();
    }

    int top() {
        if(stk.top() <= 0){
            return minNum;
        }
        return minNum + stk.top();
    }

    int getMin() {
        return minNum;
    }
};

在lc上跑有overflow的情况，所以改成 stack

0 赞同 0 条回复

桎梏普通 2023年7月11日下午4:13

class MinStack {
    // 记录每个元素与【未压入】该元素时栈中最小元素的差值
    LinkedList<Long> stack;
    // 当前【已压入】栈中元素的最小值
    private long min;
    public MinStack() {
        stack = new LinkedList();
    }

    public void push(int val) {
        // 压入第一个元素
        if(stack.isEmpty()){
            min = val;
            stack.addFirst(0L);
            return;
        }
        // 栈不为空时，每次压入计算与min的差值后压入结果
        stack.push((long)val-min);
        // 更新min
        min = Math.min((long)val,min);
    }

    public void pop() {
        long pop = stack.removeFirst();
        // 当弹出元素小于0时，说明弹出元素是当前栈中的最小值，要更新最小值
        if(pop<0){
            long lastMin = min;
            min = lastMin - pop;
        }
    }

    public int top() {
        long peek = stack.peek();
        // 若当前栈顶小于等于0，说明最小值就是栈顶元素
        if(peek<=0) return (int)min;
        // 否则就是min+peek
        return (int)(min+peek);
    }

    public int getMin() {
        return (int)min;
    }
}

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【基本数据结构】变形题：最小栈的最优解

共以下 28 个回答

# 回答此问题 取消回复

# 回答此问题取消回复