国外设计网站 绿色的,做网站开发有前途吗,手机怎么进入pc端,wordpress签到功能【问题描述】[中等]
定义栈的数据结构#xff0c;请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中#xff0c;调用 min、push 及 pop 的时间复杂度都是 O(1)。示例:MinStack minStack new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-…【问题描述】[中等]
定义栈的数据结构请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中调用 min、push 及 pop 的时间复杂度都是 O(1)。示例:MinStack minStack new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); -- 返回 -3.
minStack.pop();
minStack.top(); -- 返回 0.
minStack.min(); -- 返回 -2.
【解答思路】
1. 单栈
时间复杂度O(N^2) 空间复杂度O(1) class MinStack {private LinkedListInteger data;private int min;/** initialize your data structure here. */public MinStack() {data new LinkedListInteger();min Integer.MAX_VALUE;}public void push(int x) {if(x min){data.add(min);min x;}data.add(x);}public void pop() {if(data.pollLast() min){//flush the minmin data.pollLast();}}public int top() {return data.peekLast();}public int min() {return min;}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj new MinStack();* obj.push(x);* obj.pop();* int param_3 obj.top();* int param_4 obj.min();*/
Stack
class MinStack {private StackInteger stack;private int min;/** initialize your data structure here. */public MinStack() {stack new Stack();min Integer.MAX_VALUE;}public void push(int x) {if(x min ){//注意这里要使用号stack.push(min);//在每一个min入栈之前将它前一个min入栈min x;}stack.push(x);}public void pop() {if(stack.pop() min){//如果取出来的是当前min就将压在它低下的前一个min出栈min stack.pop();}}public int top() {return stack.peek();}public int min() {return min;}
}
2. 双栈辅助栈 时间复杂度O(1) 空间复杂度O(N)
class MinStack {StackInteger stack;StackInteger minStack;/** initialize your data structure here. */public MinStack() {stack new Stack();minStack new Stack();minStack.push(Integer.MAX_VALUE);}public void push(int x) {stack.push(x);if(x minStack.peek()){minStack.push(x);}}public void pop() {int min minStack.peek();if(stack.peek() min){minStack.pop();}stack.pop();}public int top() {return stack.peek();}public int min() {return minStack.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj new MinStack();* obj.push(x);* obj.pop();* int param_3 obj.top();* int param_4 obj.min();*/
class MinStack {StackInteger A, B;public MinStack() {A new Stack();B new Stack();}public void push(int x) {A.add(x);if(B.empty() || B.peek() x)B.add(x);}public void pop() {if(A.pop().equals(B.peek()))B.pop();}public int top() {return A.peek();}public int min() {return B.peek();}
}
【总结】
1.Stack 的常用方法
push( num) 入栈
pop() 栈顶元素出栈
empty() 判定栈是否为空
peek() 获取栈顶元素
search(num) 判端元素num是否在栈中如果在返回1不在返回-1。 注意pop()和peek()的区别。pop()会弹出栈顶元素并返回栈顶的值peek()只是获取栈顶的值但是并不会把元素从栈顶弹出来 2.Queue Queue是在两端出入的List所以也可以用数组或链表来实现。
add 增加一个元索 如果队列已满则抛出一个IIIegaISlabEepeplian异常remove 移除并返回队列头部的元素 如果队列为空则抛出一个NoSuchElementException异常element 返回队列头部的元素 如果队列为空则抛出一个NoSuchElementException异常offer 添加一个元素并返回true 如果队列已满则返回falsepoll 移除并返问队列头部的元素 如果队列为空则返回nullpeek 返回队列头部的元素 如果队列为空则返回nullput 添加一个元素 如果队列满则阻塞take 移除并返回队列头部的元素 如果队列为空则阻塞
注意 remove、element、offer 、poll、peek 其实是属于Queue接口。 add remove element操作在队满或者队空的时候会报异常。 offer poll peek 在队满或者队空的时候不会报异常。 put take操作属于阻塞操作。队满队空均会阻塞。
3.LinkedList
以双向链表实现的LinkedList既是List也是Queue。它是唯一一个允许放入null的Queue。
4. 单栈双栈思想均要掌握 面试算法常考题
参考链接https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/mian-shi-ti-30-bao-han-minhan-shu-de-zhan-fu-zhu-z/
参考链接https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/java-jian-ji-wu-fu-zhu-zhan-by-rabbitzhao/
参考链接https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/shuang-zhan-wei-hu-jie-fa-ji-linkedlistjie-fa-by-c/
