首页 > 代码库 > 算法学习 - 最小栈的实现O(1)时间

算法学习 - 最小栈的实现O(1)时间

2024-08-06 06:43:09   219人阅读

最小栈

最小栈其实和栈没有什么区别的，唯一的区别在于最小栈是可以在O(1)时间内得到当前的栈空间里，最小的值是多少。

最小栈的操作

最小栈的操作和普通栈的操作没有太大区别，唯一多了一个方法就是getMin()方法，这个方法是用来获取当前栈内的最小值。其他方法就是Push(), Pop(), Top()...等

在O(n)时间内找到新的最小值

这里就厉害了，先说普通的O(n)的方法~得到栈内最小值。是不是只要维护一个Min的变量就可以呢？不仅仅是！下面举例说明。

  • 首先：我们设置一个栈，和一个变量int Min保存最小值。
  • 然后：假设我们的操作为-Push(1),Push(2),Push(3),Push(-1),Push(4)
  • 现在：我们来看下堆栈和Min的变化。
      stack   1    2    3    -1     4
   Min    1    1    1    -1    -1

我们发现Min值是在第一次插入1的时候为1，第4次插入-1的时候变为-1，这个时候我们是不是觉得很简单，只用维护一个Min就可以了？不是的！假设我们进行操作：Pop(),Pop()操作。我们来看看堆栈里剩下了什么。

      stack   1   2   3

那么Min呢？还是-1，但其实-1已经被Pop()掉了。假如我们发现最小值被Pop()之后，我们如何更新Min呢？只能从头遍历，那么就需要O(n)的时间。

O(1)的办法

这里说下如何O(1)时间内就找到，维护的变量没有变化，但是我们在堆栈内存放的元素需要与Min值产生关联。
例子：
我们进行同样的5次Push操作，压栈顺序为1 2 3 -1 4。

  1. 第一次栈存放0, Min为1.
  2. 第二次栈存放2-Min=1, Min<2 所以继续为1.
  3. 第三次栈存放3-Min=2, Min<3 所以继续为1.
  4. 第四次栈存放-1-Min=-2, Min>-1 所以Min = -1.
  5. 第五次栈存放4-Min=5, Min<5 所以继续为-1.

大家看明白没？我们存放的数为x-Min.
这是Push的操作，当我们进行Pop()的时候怎么做呢,进行两次Pop()？

第一次栈顶元素5， 5>0, 弹出，返回 5+Min=4.
第二次栈顶元素-2, -2<0,弹出，返回Min. 并更新Min=Min-(-2).

那Top呢？

假如栈顶元素为5, 5>0 返回5+Min.
假如栈顶元素为-2, -2<0 返回Min.

大家发现没？实际上我们压栈的时候，压入的元素就是X-Min，那么只要压入的元素大于Min，那么存放的都是正数，而当X小于Min的时候，压入的元素(X-Min)就是负数。

所以弹栈的时候：
遇到正数，直接弹出栈顶元素(X-Min)和Min的和(X-Min+Min)就可以了。
遇到负数，说明在压入这个元素的时候Min值有更新，那个时候的Min值被更新为新插入的X. 例如Min=1,插入-1的时候，栈存放-1-Min=-2,而Min更新为新的X值(-1).则弹的时候就直接弹出Min就可以了。那么我们同时也把最小值弹出了，要更新Min,更新为当前Min-(X-下一个Min)此处比较绕，多用例子理解。

代码实现

我实现了4个版本，其中前两个版本是O(1)级别的，后两个是O(n)级别的。第2个版本可能有些瑕疵，假如你们看到代码哪里错误请评论，多谢。

1号容器实现

自己写的结构体。

//
//  main.cpp
//  MinStack2
//
//  Created by Alps on 14/12/3.
//  Copyright (c) 2014年 chen. All rights reserved.
//

#include <iostream>
#include <vector>
using namespace std;
class MinStack {
public:
    vector<int> stack;
    int min;
    void push(int x) {
        if (stack.empty()) {
            stack.push_back(0);
            min = x;
        }else{
            stack.push_back(x-min);
            if (x < min) {
                min = x;
            }
        }
        
    }
    
    void pop() {
        if (stack.empty()) {
            return;
        }else{
            if (stack.back() < 0) {
                min = min - stack.back();
            }
            stack.pop_back();
        }
    }
    
    int top() {
        if (stack.empty()) {
            return NULL;
        }
        if (stack.back() > 0) {
            return stack.back()+min;
        }else{
            return min;
        }
    }
    
    int getMin() {
        if (stack.empty()) {
            return NULL;
        }
        return min;
    }
};

int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";
    return 0;
}


2号STL的stack实现

在边缘测试的时候，我的编译器没出错，但是OJ上报WA了。

//
//  main.cpp
//  MinStack4_leetcode
//
//  Created by Alps on 14/12/3.
//  Copyright (c) 2014年 chen. All rights reserved.
//

#include <iostream>
#include <stack>
using namespace std;

class MinStack{
public:
    stack<long> s;
    long min;
    void push(int x){
        if (s.empty()) {
            s.push(0);
            min = x;
        }else{
            s.push(x-min);
            if (x < min) {
                min = x;
            }
        }
    }
    
    void pop(){
        if (s.empty()) {
            return;
        }else{
            if (s.top() < 0) {
                min = min - s.top();
            }
            s.pop();
        }
    }
    
    int top(){
        if (s.empty()) {
            return NULL;
        }else{
            if (s.top() > 0) {
                return (int)(min+s.top());
            }else{
                return (int)min;
            }
        }
    }
    
    int getMin(){
        if (s.empty()) {
            return NULL;
        }else{
            return (int)min;
        }
    }
    
};

int main(int argc, const char * argv[]) {
    int a = -2147483648;
    
    MinStack M;
    M.push(2147483646);
    M.push(2147483646);
    M.push(2147483647);
    printf("%d\n",M.top());
    M.pop();
    printf("%d\n",M.getMin());
    M.pop();
    printf("%d\n",M.getMin());
    M.pop();
    M.push(2147483647);
    printf("%d\n",M.top());
    printf("%d\n",M.getMin());
    M.push(a);
    printf("%d\n",M.top());
    printf("%d\n",M.getMin());
    M.pop();
    printf("%d\n",M.getMin());
    return 0;
}


3号链表实现

自己写的链表结构体。

//
//  main.cpp
//  MinStack3_leetcode
//
//  Created by Alps on 14/12/3.
//  Copyright (c) 2014年 chen. All rights reserved.
//

#include <iostream>
using namespace std;

class MinStack {
public:
    
    struct StackNode{
        int num;
        StackNode *next;
    };
    typedef StackNode* stack;
    stack s;
    MinStack(){
        s = (stack)malloc(sizeof(struct StackNode));
        s->next = NULL;
    }
    
    int min;
    void push(int x) {
        if (s->next == NULL) {
            stack node = (stack)malloc(sizeof(struct StackNode));
            node->num = x;
            node->next = s->next;
            s->next = node;
            min = x;
        }else{
            stack node = (stack)malloc(sizeof(struct StackNode));
            node->num = x;
            node->next = s->next;
            s->next = node;
            if (x < min) {
                min = x;
            }
        }
    }
    
    void pop() {
        if (s->next == NULL) {
            return;
        }else{
            stack temp = s->next;
            if (min == s->next->num && s->next->next != NULL) {
                
                s->next = s->next->next;
                free(temp);
                min = s->next->num;
                for (stack loop = s->next; loop != NULL; loop = loop->next) {
                    if (min > loop->num) {
                        min = loop->num;
                    }
                }
            }else{
                
                s->next = s->next->next;
                free(temp);
            }
            
        }
    }
    
    int top() {
        if (s->next == NULL) {
            return NULL;
        }
        return s->next->num;
    }
    
    int getMin() {
        if (s->next == NULL) {
            return NULL;
        }
        return min;
    }
};

int main(int argc, const char * argv[]) {
    MinStack MinS;
    MinS.push(-1);
    MinS.push(0);
    MinS.push(2);
    MinS.push(-2);
    printf("%d\n",MinS.top());
    MinS.pop();
    MinS.pop();
    MinS.pop();
    printf("%d\n",MinS.getMin());
    return 0;
}


4号容器实现

最古老的版本。

//
//  main.cpp
//  MinStack_leetcode
//
//  Created by Alps on 14/12/2.
//  Copyright (c) 2014年 chen. All rights reserved.
//

#include <iostream>
#include "vector"
using namespace std;

class MinStack {
public:
    struct StackNode{
        int num;
        int min;
    };
    vector<StackNode> stack;
    void push(int x) {
        if (stack.empty()) {
            StackNode S = {x,x};
            stack.push_back(S);
        }else{
            if (x < stack.back().min) {
                StackNode S = {x,x};
                stack.push_back(S);
            }else{
                StackNode S = {x,stack.back().min};
                stack.push_back(S);
            }
        }
        
    }
    
    void pop() {
        if (stack.empty()) {
            
        }else{
            stack.pop_back();
        }
    }
    
    int top() {
        if (stack.empty()) {
            return NULL;
        }
        return stack.back().num;
    }
    
    int getMin() {
        if (stack.empty()) {
            return NULL;
        }
        return stack.back().min;
    }
};

int main(int argc, const char * argv[]) {
    MinStack minstack;
    minstack.push(-1);
    minstack.push(1);
    printf("%d %d\n",minstack.top(), minstack.getMin());
    return 0;
}


算法学习 - 最小栈的实现O(1)时间


联系
我们