The title

LeetCode problem 155. Association type: 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], [], [], [], []] 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 (); Tip: pop, top, and getMin operations are always called on a non-empty stack.Copy the code

Time to solve the problem.

class MinStack { /** * initialize your data structure here. */ public MinStack() { } public void push(int val) { } public void pop() { } public int top() { } public int getMin() { } } /** * 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(); * /Copy the code

The method input parameters are given above to complete the answer.

Subject analysis

  1. The idea is to use a List to implement the problem
  2. Use a List to store data and an int value to hold the minimum value
  3. Update the minimum each time you push and pop

Answers to analysis

This article only analysis I do the idea, only for reference, to understand a solution to the idea, other kinds of ideas to do the problem please access the Internet.

Answer successful: Execution time :6 ms, beat 97.24% of Java users memory consumption :40.3 MB, beat 27.28% of Java users

import java.util.ArrayList; //leetcode submit region begin(Prohibit modification and deletion) class MinStack { int minNum; List<Integer> mList; /** * initialize your data structure here. */ public MinStack() { mList = new ArrayList<>(); } public void push(int val) { if (mList.size() == 0) { minNum = val; } else { minNum = val < minNum ? val : minNum; } mList.add(val); } public void pop() { if (mList.get(mList.size() - 1) == minNum && mList.size() > 1) { mList.remove(mList.size() - 1); minNum = mList.get(0); for (int i = 0; i < mList.size(); i++) { minNum = mList.get(i) < minNum ? mList.get(i) : minNum; } } else { mList.remove(mList.size() - 1); } } public int top() { return mList.get(mList.size() - 1); } public int getMin() { return minNum; }}Copy the code