【剑指Offer】No.30 包含min函数的栈

剑指Offer】No.30 包含min函数的栈"/>

【剑指Offer】No.30 包含min函数的栈

题目描述

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

解题思路

画抽象为具体。以具体的例子进行分析，会出现什么问题，我们应该如何处理？

import java.util.Stack;public class Solution {// stack1是我们的数据栈，保留数据入栈的顺序// stack2是我们的辅助栈，用来存储每一个元素入栈时与当前栈中最小值的比较之后得到的最小值// stack1与stack2的长度一致，同时存储同时删除private Stack<Integer> stack1 = new Stack<Integer>();private Stack<Integer> stack2 = new Stack<Integer>();public void push(int node) {stack1.push(node);// stack2为空则直接存储当前元素最为最小值if (stack2.isEmpty()) {stack2.push(node);} else {// stack2非空，则判断当前元素与栈顶元素大小，存储较小元素即可if (stack2.peek() <= node) {stack2.push(stack2.peek());} else {stack2.push(node);}}}public void pop() {// 同时pop栈顶元素，保持栈长度时刻一致stack1.pop();stack2.pop();}public int top() { // 获取数据栈栈顶元素return stack1.peek();}public int min() { // 获取辅助栈栈顶元素return stack2.peek();}
}