包含min函数的最小栈

古城微笑少年丶 2022-07-24 06:18 163阅读 0赞

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min,push，及pop的时间复杂度都是O(1)。

剑指offer上面的题目。废话不多说，直接上代码：

#include "stdafx.h"
    #include <assert.h>
    #include <iostream>
    #include <stack>
    using namespace std;
    template <class T>
    class StackWithMin
    {
    public:
    	void push(const T& value);
    	void pop();
    	const T& top()const;
    	const T& min()const;
    private:
    	stack<T> m_data;//数据栈
    	stack<T> m_min;//最小栈（辅助栈）
    };
    template <class T>
    void StackWithMin<T>::push(const T& value)
    {
    	m_data.push(value);
    	if (m_min.empty() || value < m_min.top())
    	{
    		m_min.push(value);
    	}
    	else
    	{
    		m_min.push(m_min.top());
    	}
    }
    template <class T>
    void StackWithMin<T>::pop()
    {
    	assert(!m_data.empty()&&!m_min.empty());
    	m_data.pop();
    	m_min.pop();
    }
    template <class T>
    const T& StackWithMin<T>::min()const
    {
    	assert(!m_min.empty());
    	return m_min.top();
    }
    template <class T>
    const T& StackWithMin<T>::top()const
    {
    	assert(!m_data.empty());
    	return m_data.top();
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	StackWithMin<int> smin;
    	smin.push(3);
    	smin.push(4);
    	smin.push(2);
    	smin.push(1);
    	cout << smin.top() << endl;
    	cout << smin.min() << endl;
    	smin.pop();
    	cout << smin.top() << endl;
    	cout << smin.min() << endl;
    	smin.pop();
    	cout << smin.top() << endl;
    	cout << smin.min() << endl;
    	smin.pop();
    	system("pause");
    	return 0;
    }

leetcode上面也有一道类似的题目。

题目地址：https://leetcode.com/problems/min-stack/

我的solution:

class MinStack {
    public:
          MinStack()
         {
             top_index=-1;
             min=INT_MAX;
         }
        void push(int x) {
            if(top_index<0)
            {
                min=INT_MAX;
            }
            top_index++;
            stack[top_index]=x;
            if(x<min) 
            {
                mindata[top_index]=x;
                min=x;
            }
            else 
            {
               mindata[top_index]=min;
            }
            
        }
    
        void pop() {
            top_index--;
            min=mindata[top_index];
        }
    
        int top() {
            return stack[top_index];
        }
    
        int getMin() {
            return mindata[top_index];
        }
    private:
        int stack[100000];
        int mindata[100000];
        int top_index;
        int min;
    };