2.设计包含min函数的栈(栈)
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。package cn.emma.interview_2;
public class Stack {
public final static int MAX = 100;
private static int top;
private static int[] S = new int[MAX];
static int min;
private static Stack minStack = new Stack();
public boolean emptyStack(){
if(top == 0){
return true;
}
return false;
}
public static void push(int x){
if(top == 0){
min =x;
}
else{
min = (S[min] > x) ? ++top:min;
}
minStack.push(min);
S[top] = x;
}
public static int pop(){
minStack.pop();
return S[--top];
}
public static int minElement(){
return minStack.S[minStack.top];
}
public static int getMin(){
return min;
}
public static void main(String[] args) {
push(0);push(-1);
push(2);
push(-9);
push(10);
System.out.println(pop() + "\t" + pop() + "\t" + pop());
System.out.println(minElement());
}
}
分享到:
相关推荐
本微软面试100题系列,共计11篇文章,300多道面试题,截取本blog索引性文章:程序员面试、算法研究、编程艺术、红黑树、数据挖掘5大系列集锦:http://blog.csdn.net/v_july_v/article/details/6543438,中的第一部分...
ms100(微软面试100题)答案整理版
本微软面试100题系列,共计11篇文章,300多道面试题,截取本blog索引性文章:程序员面试、算法研究、编程艺术、红黑树、数据挖掘5大系列集锦:http://blog.csdn.net/v_july_v/article/details/6543438,中的第一部分...
微软面试100题完整版(题目答案齐全) 微软面试100题完整版(题目答案齐全) 微软面试100题完整版(题目答案齐全) 微软面试100题完整版(题目答案齐全)
微软面试100题(含参考答案)
本微软面试100题系列,共计11篇文章,300多道面试题,祝大家都能找到令自己满意的工作
微软面试100题 doc版
面试_微软面试100题全部答案.docx
CSDN著名博客《结构之法算法之道》中的“微软面试100题系列”的11篇文章整理而成的PDF,带目录。
算法永远是王道(含微软面试100题) (把二元查找树转变成排序的双向链表;设计包含min函数的栈;求子数组的最大和;在二元树中找出和为某一值的所有路径;查找最小的k个元素等)