Day5-线性表-栈-最小栈问题

BUPTrenyi

发布于 2019-07-16 03:06:49

33300

代码可运行

文章被收录于专栏：算法其实很好玩算法其实很好玩

运行总次数：0

代码可运行

一先唠两句

本来昨天就应该更新栈的问题了，可为什么没有更新呢？

因为我忘了

而且今天本来按照之前说的，应该更两篇的，但是今天只有一篇盒饭，还不是因为最近需求排的紧，加班加点干活，大哥们见谅

二上车！

设计一个栈，支持如下操作：

push（x）：将元素x压入栈中

pop（）：弹出栈顶元素

top（）：返回栈顶元素

getMin（）：返回栈中最小的元素

三冷静分析

前提：栈，先进后出的数据结构，c++标准STL支持，需要“#include<stack>”

前三个操作都好说，都是常规操作

怎么实现，实时获取最小值？

这就需要用到栈、队列中的一个常规思想：再用一个栈（or队列）

引入另外一个栈，即最小栈，它的栈顶元素实时都是最小的

怎么实现呢？

冷静分析：

首先我们需要知道，最小栈和数据栈需要保持相同个数的元素？

为啥呢？

当数据栈弹出栈顶元素时，最小栈也要同时弹出栈顶，此时的栈顶，仍然为最小元素。这就保持了，不管数据栈执行什么操作，最小栈的栈顶，都是最小元素。

那么

数据栈压栈的时候，若压栈的这个数，小于等于当前最小栈栈顶元素，即它应该是新的最小值，那么最小栈压栈；

数据栈压栈的时候，若压栈的这个数，大于当前最小栈栈顶元素，则取出当前最小栈栈顶元素，讲该元素压入最小栈栈顶。

即，数据栈压栈时，最小栈也要压栈，压入当前的最小元素

有点拗口是不是，我举个例子~

第一次，栈空时，来了个-3，数据栈压栈，最小栈压栈

第二次，来了个-5，数据栈压栈-5，-5<-3，最小栈压栈-5

此时我getMin，最小栈栈顶是-5，没毛病~

第三次，来了个0，数据栈压栈0，0>-5，则最小栈再压栈当前的最小元素，即-5

第四次，我执行pop，弹出栈顶，最小栈也要弹，-5弹出

第五次，我再执行pop，最小栈再弹-5，此时最小栈栈顶是-3，getMin也是-3，没毛病

四完整代码及运行结果

//
// Created by renyi on 2019/6/3.
//
#include <iostream>
#include <stack>
using namespace std;

class MinStack{
public:
    MinStack(){
    }

    void push(int x){
        _data.push(x);//数据栈正常把元素压栈
        if(_min.empty()){
            _min.push(x);//如果最小栈是空，没元素，直接压栈
        } else{
            if (x > _min.top()){
                x = _min.top();//如果x大于最小栈的栈顶，则取出最小栈的栈顶，赋值给x，以便后面的压栈
            }
            _min.push(x);//不管怎样，都会将当前最小的元素压栈，保证和数据栈元素个数相同
        }
    }

    void pop(){
        _data.pop();//出栈，大家都出栈，保持元素个数相同
        _min.pop();
    }

    int top(){
        return _data.top();//top就正常返回数据栈的栈顶
    }

    int getMin(){
        return _min.top();//getmin就是返回最小栈的栈顶
    }

private:
    stack<int> _data;//数据栈
    stack<int> _min;//最小栈
};

int main(){
    MinStack minStack;
    minStack.push(-3);//先压栈3，此时getmin应该是-3
    printf("top:[%d]\n", minStack.top());
    printf("min:[%d]\n\n", minStack.getMin());

    minStack.push(-5);//此时getmin应该是-5
    printf("top:[%d]\n", minStack.top());
    printf("min:[%d]\n\n", minStack.getMin());

    minStack.push(-7);//此时getmin应该是-7
    printf("top:[%d]\n", minStack.top());
    printf("min:[%d]\n\n", minStack.getMin());

    minStack.pop();//此时执行了pop（），-7出栈了，getmin应该是-5
    printf("top:[%d]\n", minStack.top());
    printf("min:[%d]\n\n", minStack.getMin());

    minStack.push(0);//0入栈，此时getmin还是-5
    printf("top:[%d]\n", minStack.top());
    printf("min:[%d]\n\n", minStack.getMin());
    return 0;
}