Java教程

力扣刷题13

本文主要是介绍力扣刷题13,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

剑指 Offer 30. 包含min函数的栈
定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 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.
定义新的数据结构:需要两个栈实现,一个是最小栈,一个是主栈,
首先在构造函数中实例化两个对象
然后对于push函数,主栈直接push元素,但是最小栈需要判断栈顶元素是否大于新元素,也就是说新元素是否是最小元素,是的话就直接入栈,或者最小栈中没有元素,也直接入栈这样的话就可以保障最小栈的栈顶元素是最小的
对于pop函数,主栈弹出元素的时候,需要判断弹出元素是否是最小栈栈顶元素,是的话最小栈也跟着一起弹出,维护一下最下栈,
最后top就直接返回主栈栈顶
min函数返回最小栈的栈顶

class MinStack {
Stack<Integer> stackA;
Stack<Integer> stackB;
    /** initialize your data structure here. */

    public MinStack() {
        stackA=new Stack<>();
        stackB=new Stack<>();
    }
    
    public void push(int x) {

        stackA.push(x);
        if(stackB.isEmpty()||stackB.peek()>=x){
            stackB.push(x);
        }
    }
    
    public void pop() {
     
             if(stackA.pop().equals(stackB.peek())){
          stackB.pop();
      }
    }
    
    public int top() {
      return stackA.peek();
    }
    
    public int min() {
       return stackB.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();
 */
这篇关于力扣刷题13的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!