最新公告
  • 欢迎您光临波比源码,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 算法学习 – 最小栈的实现O(1)时间


    最小栈

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

    最小栈的操作

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

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

    这里就利害了,先说普通的O(n)的方法~得到栈内最小值。是否是只要保护1个Min的变量就能够呢?不单单是!下面举例说明。

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

    我们发现Min值是在第1次插入1的时候为1,第4次插入的时候变成,这个时候我们是否是觉得很简单,只用保护1个Min就能够了?不是的!假定我们进行操作:Pop(),Pop()操作。我们来看看堆栈里剩下了甚么。

    stack 1 2 3

    那末Min呢?还是,但其实已被Pop()掉了。假设我们发现最小值被Pop()以后,我们如何更新Min呢?只能从头遍历,那末就需要O(n)的时间。

    O(1)的办法

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

    1. 第1次栈寄存0, Min为1.
    2. 第2次栈寄存2-Min=1, Min<2 所以继续为1.
    3. 第3次栈寄存3-Min=2, Min<3 所以继续为1.
    4. 第4次栈寄存⑴-Min=⑵, Min>⑴ 所以Min = ⑴.
    5. 第5次栈寄存4-Min=5, Min<5 所以继续为⑴.

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

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

    那Top呢?

    假设栈顶元素为5, 5>0 返回5+Min.
    假设栈顶元素为⑵, ⑵<0 返回Min.

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

    所以弹栈的时候:
    遇到正数,直接弹出栈顶元素(X-Min)和Min的和(X-Min+Min)就能够了。
    遇到负数,说明在压入这个元素的时候Min值有更新,那个时候的Min值被更新为新插入的X. 例如Min=1,插入⑴的时候,栈寄存⑴-Min=⑵,而Min更新为新的X值(⑴).则弹的时候就直接弹出Min就能够了。那末我们同时也把最小值弹出了,要更新Min,更新为当前Min-(X-下1个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!
    ";
    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 = ⑵147483648;

    MinStack M;
    M.push(2147483646);
    M.push(2147483646);
    M.push(2147483647);
    printf("%d
    ",M.top());
    M.pop();
    printf("%d
    ",M.getMin());
    M.pop();
    printf("%d
    ",M.getMin());
    M.pop();
    M.push(2147483647);
    printf("%d
    ",M.top());
    printf("%d
    ",M.getMin());
    M.push(a);
    printf("%d
    ",M.top());
    printf("%d
    ",M.getMin());
    M.pop();
    printf("%d
    ",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(⑴);
    MinS.push(0);
    MinS.push(2);
    MinS.push(⑵);
    printf("%d
    ",MinS.top());
    MinS.pop();
    MinS.pop();
    MinS.pop();
    printf("%d
    ",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(⑴);
    minstack.push(1);
    printf("%d %d
    ",minstack.top(), minstack.getMin());
    return 0;
    }

    波比源码 – 精品源码模版分享 | www.bobi11.com
    1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
    2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
    3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
    4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
    5. 如有链接无法下载、失效或广告,请联系管理员处理!
    6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
    7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

    波比源码 » 算法学习 – 最小栈的实现O(1)时间

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    波比源码
    一个高级程序员模板开发平台
    升级波友尊享更多特权立即升级