建站平台 绑定域名,建设银行租房平台网站6,php按步骤做网站,做投融资平台的网站都有哪些题目
定义栈的数据结构#xff0c;请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中#xff0c;调用 min、push 及 pop 的时间复杂度都是 O(1)。 示例: MinStack minStack new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack…题目
定义栈的数据结构请在该类型中实现一个能够得到栈的最小元素的 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.提示
各函数的调用总次数不超过 20000 次 解题思路 1.题目要求我们实现一个能够得到栈的最小元素的 min 函数且调用 min、push 及 pop 的时间复杂度都是 O(1)。我们需要用到两个栈去解决这个问题。 2.举个例子 下面我们开始进行入栈操作在入栈第一个元素时Stack1直接入栈而当Stack2为空时我们也将元素直接入栈。 在入栈第二个元素时Stack1依旧直接入栈这时我们发现要入栈的元素大于Stack2的栈顶元素所以我们不对Stack2进行入栈操作 以下入栈操作的思路相同Stack1正常入栈Stack2只有在空的时候或者栈顶元素大于被入栈元素时才进行入栈。 此时入栈操作全部执行结束我们来看看出栈操作 在出栈操作时我们需要先判断Stack1是否为空要保证我们有元素可以出栈当Stack1不为空时Stack2一定也不为空。然后我们将Stack1的栈顶元素与Stack2的栈顶元素进行比较若两元素不同则只将Stack1进行出栈否则就要将Stack1和Stack2同时出栈。 出栈操作执行结束。 3还有最后两个方法pop求栈顶元素时我们只需要返回Stack1的栈顶即可min求栈中最小元素时我们只需要返回Stack2的栈顶元素即可。 代码实现
class MinStack {StackInteger Stack1;StackInteger Stack2;/** initialize your data structure here. */public MinStack() {Stack1 new Stack();Stack2 new Stack();}public void push(int x) {Stack1.push(x);if(Stack2.isEmpty() || x Stack2.peek() ){Stack2.push(x);}}public void pop() {if(!Stack1.isEmpty()){//数值大于 127比较的就是一个对象if(Stack1.peek().intValue() Stack2.peek().intValue()){Stack2.pop();}Stack1.pop();}}public int top() {return Stack1.peek();}public int min() {return Stack2.peek();}
} 测试结果
