This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is the 155 minimum stack on LeetCode, the difficulty is simple.

Tag: stack

Design a stack that supports push, pop, and top operations and can retrieve the smallest element in constant time.

  • Push (x) – Pushes element X onto the stack.
  • Pop () — Removes the top element of the stack.
  • Top () — Gets the top element on the stack.
  • GetMin () — Retrieves the smallest element in the stack.

Example:

Input: [" MinStack ", "push" and "push" and "push" and "getMin", "pop", "top", "getMin"] [[], [2], [0], [3], [], [], [], []]Copy the code

Output:

[null,null,null,null,-3, NULL,0,-2] 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 (); -- -- > to return to 2.Copy the code

Tip:

  • Pop, top, and getMin operations are always called on a non-empty stack.

Double stack method

To quickly find the smallest element in the stack, we can use a secondary stack help.

This is achieved by controlling the stack logic of Help: the minimum value of elements in the stack is always stored at the top of the help stack.

Code:

class MinStack {
    Deque<Integer> data = new ArrayDeque<>();
    Deque<Integer> help = new ArrayDeque<>();

    public void push(int val) {
        data.addLast(val);
        if (help.isEmpty() || help.peekLast() >= val) {
            help.addLast(val);
        } else{ help.addLast(help.peekLast()); }}public void pop(a) {
        data.pollLast();
        help.pollLast();
    }
    
    public int top(a) {
        return data.peekLast();
    }
    
    public int getMin(a) {
        returnhelp.peekLast(); }}Copy the code
  • Time complexity: all operations are O(1)O(1)O(1)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.155 article in our “Brush through LeetCode” series, which started from 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.