preface

Before we get into the minimum-stack algorithm, let’s take a look at how data structure stacks are implemented in Java.

The Stack inherits from the thread-safe Vector array. Since the Stack inherits from the Vector array, the Stack also has the methods and variables that the Vector declares public. Stack is genetically programmed to support dynamic expansion. But Stack for a higher level of abstraction, does not provide such a method, and handed over to the enhanced version of the Deque queue implementation, see, Stack is just a limited queue.

Let’s follow the top notes for an overview of ArrayDeque.

Obviously, it supports dynamic scaling, but also provides push,pop,peek,poll, etc. If stacks can be implemented with arrays, then lists can be implemented with arrays

We found LinkedList to be an all-rounder, a List, a Queue, and a Deque. But when we use it, we always refer to it with a specific interface, because the code that holds the interface is more abstract, and the methods defined by the interface themselves represent a specific purpose.

StackStack = new Stack<>()!

Minimum stack

1.1 Problem Description

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.

1.2 Ideas and complexity analysis

The core of the minimum stack problem is to retrieve the minimum element in constant time, that is, we need a memory space to store the minimum value in real time. What data structure is used to implement this memory space?

Obviously, it is possible to declare a minimum global variable, and it is also possible to automatically move the pointer to the top of the stack. Here we only introduce the idea of using the stack, and its specific implementation is as follows:

When the stack is pressed, the element to be pushed is compared with the element of the minimum stack, and the minimum stack is updated if it is smaller. To get a minimum, peek() pops the top element of the minimum stack. It does look easy, if you think so, it is necessary to continue to read

If we delete the top element of the stack first, then the top element of the minimum stack needs to be updated synchronously, but WE do not save the last minimum at all, what can we do

A popular solution is to insert the minimum as the top element of the stack instead of updating the original minimum when pushed onto the minimum stack. This can solve the problem, and even the performance is perfectly reasonable, but can you use only one stack to store the minimum and data at the same time?

That’s where Node comes in. Let’s first look at how Node is used in Java source code

Similarly, we can use data and minimum values as Node attributes by analogy with key and Value:

private static class Node{
    private int val;
    private int min;
    public Node(int val,int min){
      this.val = val;
      this.min = min; }}Copy the code

Using a stack solution, because every minimum value is stored, results in slightly lower performance than using a secondary stack, but the code is readable and well worth trying.

Let’s briefly look at the complexity analysis of the two solutions:

  1. Auxiliary stack: Time complexity O(1). Space complexity O(N)
  2. A stack: Time complexity O(1), space complexity O(N), but because applying for a stack space is less than applying for multiple Node pairs, the space complexity is higher than that of the auxiliary stack.

1.3 Interesting Diagram

Auxiliary stack

A stack

Please move to the comment area: leetcode-cn.com/problems/mi…

1.4 Code Demonstration

/** * class MinStack {private Stack
      
        Stack; /** initialize your data structure here. */
      
    public MinStack(a) {
        stack = new Stack<>();
    }
    
    public void push(int x) {
        if(stack.empty())
            stack.push(new Node(x, x));
        else
            stack.push(new Node(x, Math.min(x,stack.peek().min)));
    }
    
    public void pop(a) {
        stack.pop();
    }
    public int top(a){
        return stack.peek().val;
    }
    
    public Integer getMin(a){
        return stack.peek().min;
    }
    private static class Node{
        private int val;
        private int min;
        public Node(int val,int min){
            this.val = val;
            this.min = min; }}}/** * auxiliary stack solution */
class MinStack {
    / / the data stack
    Stack<Integer> dataStack = null;
    // Minimum stack
    Stack<Integer> minStack = null;
    /** initialize your data structure here. */
    public MinStack(a) {
        dataStack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }
    
    public void push(int x) {
        dataStack.push(x);
        if(minStack.isEmpty() || x<=minStack.peek())
            minStack.push(x);
    }
    
    public void pop(a) {
        if(dataStack.pop().equals(minStack.peek())){ minStack.pop(); }}public int top(a) {
        return dataStack.peek();
    }
    
    public Integer getMin(a){
        if(! minStack.isEmpty())return minStack.peek();
        //throw new EmptyStackException();
        return null; }}Copy the code

Day arch a pawn, work does not donate tang.