剑指Offer-20.包含min函数的栈(C++/Java)

题目：

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

分析：

因为题目要求得到栈中最小元素的min函数时间复杂度为O(1)，这里便不选择遍历栈内元素的方法了。

我们新建立一个StackMin栈，StackMin栈内的元素个数应该与数据栈内的元素个数保持一致，StackMin栈顶元素是当前数据栈中的最小元素。

也就是说，在将一个数据压入栈中，同时要讲此时的最小元素压入StackMin，因为从最开始就将栈的最小值压入栈中，每当新来一个元素，就和StackMin中栈顶元素比较，如果新元素小，就将新元素压入，否则就将StackMin的栈顶元素压入，当需要求min时，直接返回StackMin的栈顶元素即可。

程序：

C++

class Solution {

public:

    void push(int value) {

        s.push(value);

        if(minStack.size() == )

            minStack.push(value);

        else{

            if(minStack.top() > value)

                minStack.push(value);

            else

                minStack.push(minStack.top());

        }

    }

    void pop() {

        s.pop();

        minStack.pop();

    }

    int top() {

        return s.top();

    }

    int min() {

        return minStack.top();

    }

private:

    stack<int> s;

    stack<int> minStack;

};

Java

import java.util.Stack;

public class Solution {

    public void push(int node) {

        sData.push(node);

        if(sMin.empty())

            sMin.push(node);

        else{

            if(node < sMin.peek())

                sMin.push(node);

            else

                sMin.push(sMin.peek());

        }

    }

    public void pop() {

        sData.pop();

        sMin.pop();

    }

    public int top() {

        return sData.peek();

    }

    public int min() {

        return sMin.peek();

    }

    private Stack<Integer> sData = new Stack<>();

    private Stack<Integer> sMin = new Stack<>();

}

巴特西

剑指Offer-20.包含min函数的栈(C++/Java)

题目：

分析：

程序：

最新文章

热门文章