LeetCode 155. 最小栈

发布时间:2024年01月02日

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the?MinStack?class:

  • MinStack()?initializes the stack object.
  • void push(int val)?pushes the element?val?onto the stack.
  • void pop()?removes the element on the top of the stack.
  • int top()?gets the top element of the stack.
  • int getMin()?retrieves the minimum element in the stack.

You must implement a solution with?O(1)?time complexity for each function.

Example 1:

Input

["MinStack","push","push","push","getMin","pop","top","getMin"]

[[],[-2],[0],[-3],[],[],[],[]]

Output

[null,null,null,null,-3,null,0,-2]

Explanation

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); // return -3

minStack.pop();

minStack.top(); // return 0

minStack.getMin(); // return -2

Constraints:

  • -2^31 <= val <= 2^31 - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

解法思路:

  1. 数据栈+辅助栈
  2. 数据栈

法一:?

class MinStack {
    // Time: O(1)
    // Space: O(N)
    private Deque<Integer> stack;
    private Deque<Integer> minStack;

    public MinStack() {
        stack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.addFirst(Integer.MAX_VALUE);
    }

    public void push(int val) {
        stack.addFirst(val);
        minStack.addFirst(Math.min(minStack.peek(), val));
    }

    public void pop() {
        stack.removeFirst();
        minStack.removeFirst();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

法二:?

class MinStack {
    // Time: O(1)
    // Space: O(N)
    private Deque<Integer> stack;
    private int min = Integer.MAX_VALUE;

    public MinStack() {
        stack = new LinkedList<Integer>();
    }

    public void push(int val) {
        if (val <= min) {
            stack.addFirst(min);
            min = val;
        }
        stack.addFirst(val);
    }

    public void pop() {
        if (stack.removeFirst() == min) {
            min = stack.removeFirst();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

文章来源:https://blog.csdn.net/qq_38304915/article/details/135341939
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。