做邀请函的网站,外贸网络营销的主动营销有哪些,旅游景区宣传推广方案,有系统源码可以做网站吗题目描述
设计一个支持 push#xff0c;pop#xff0c;top 操作#xff0c;并能在常数时间内检索到最小元素的栈。
push(x) – 将元素 x 推入栈中。 pop() – 删除栈顶的元素。 top() – 获取栈顶元素。 getMin() – 检索栈中的最小元素。 示例:
MinStack minStack new …题目描述
设计一个支持 pushpoptop 操作并能在常数时间内检索到最小元素的栈。
push(x) – 将元素 x 推入栈中。 pop() – 删除栈顶的元素。 top() – 获取栈顶元素。 getMin() – 检索栈中的最小元素。 示例:
MinStack minStack new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); -- 返回 -3.
minStack.pop();
minStack.top(); -- 返回 0.
minStack.getMin(); -- 返回 -2.解法 思路1时间换空间法不使用多余空间 代码如下
class MinStack {private ArrayListInteger list;private int min Integer.MAX_VALUE;/** initialize your data structure here. */public MinStack() {list new ArrayListInteger();}public void push(int x) {if(x min) {min x;}list.add(x);}public void pop() {int size list.size();if(size 0) {return;}int top list.get(size -1);if(top min) {int newMin Integer.MAX_VALUE;for(int i0;isize-1;i) {if(list.get(i)newMin) {newMin list.get(i);}}min newMin;}list.remove(size -1);}public int top() {int size list.size();if(size 0) {throw new RuntimeException();}return list.get(size -1);}public int getMin() {return min;}}思路2空间换时间法使用额外存储降低操作时间
/**
* 每次push两个值1元素2当前栈的最小值
* 空间换时间
* param x
*/
class MinStack {private StackInteger stack;/** initialize your data structure here. */public MinStack() {stack new StackInteger();}public void push(int x) {if(stack.isEmpty()) {stack.add(x);stack.add(x);}else {int min stack.peek();stack.add(x);stack.add(xmin?x:min);}}public void pop() {stack.pop();stack.pop();}public int top() {return stack.get(stack.size()-2);}public int getMin() {return stack.peek();}}
