蕴含min函数的栈

1. 题目形容

定义栈的数据结构，请在该类型中实现一个可能失去栈中所含最小元素的min函数（工夫复杂度应为O（1））。

2. 示例

无

3. 解题思路

思路：利用一个辅助栈来寄存最小值

栈  3，4，2，5，1辅助栈 3，3，2，2，1

每入栈一次，就与辅助栈顶比拟大小，如果小就入栈，如果大就入栈以后的辅助栈顶

当出栈时，辅助栈也要出栈

这种做法能够保障辅助栈顶肯定都以后栈的最小值

4. Java实现

import java.util.Stack; public class Solution {     private Stack<Integer> dataStack = new Stack();    private Stack<Integer> minStack = new Stack();        public void push(int node) {        dataStack.push(node);        if (minStack.isEmpty() || min() > node){ // 如果为空，则之间push进去，如果最小栈的最小值都比node大，也把node值push            minStack.push(node);         }else{            minStack.push(min());        }    }        public void pop() {        dataStack.pop();        minStack.pop();    }        public int top() {        return dataStack.peek();    }        public int min() {        return minStack.peek();    }}

5. Python实现

# -*- coding:utf-8 -*-class Solution:    def __init__(self): #应用两个栈来实现，两个栈的大小是雷同的        self.stack = []        self.minStack = []        def push(self, node):        # write code here        self.stack.append(node)        if not self.minStack or self.min() > node: # 将最小值减少到minStack中            self.minStack.append(node)        else:            self.minStack.append(self.min())            def pop(self):        # write code here        if self.stack and self.minStack:            self.stack.pop()            self.minStack.pop()        else:            return None             def top(self):        # write code here        return self.stack[-1]    def min(self):        # write code here        return self.minStack[-1]
如果您感觉本文有用，请点个“在看”