Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

One, foreword

👨🎓 Author: Bug Bacteria

✏️ blog: CSDN, Nuggets, etc

💌 public account: Magic House of the Circle of the Apes

🚫 special statement: original is not easy, reprint please attach the original source link and this article statement, thank you for your cooperation.

🙏 Copyright notice: part of the text or pictures in the article may come from the Internet or Baidu Encyclopedia, if there is infringement, please contact bug bacteria processing.

Hello, little friends, I am bug bacteria 👀. Gold three silver four, brush the month again. So whether you’re looking for a career change or a career change, get your act together and do the right thing 👣. So, quickly follow the pace of bug bacteria roll up ⏰, become strong from this moment ➕🧈.

In the process of reviewing articles, if you think the articles are helpful to you at all, please don’t be too mean with your likes and bravely light up the articles 👍. Your likes (collect ⭐️+ pay attention to 👨 port + message board) are the best encouragement and support for bugs on my creation path. Time does not abandon 🏃🏻♀️, nuggets stop 💕, cheer up 🏻

Ii. Title Description:

Topic:

Design a stack that supports push, pop, and top operations and can retrieve the smallest 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 at the top of the stack.
  • Int top() gets the element at the top of the stack.
  • Int getMin() gets the smallest element in the stack.

See the following example for details:

Example 1:

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 (); -- -- > to return to 2.Copy the code

Tip:

  •  -2^31 <= val <= 2^31 – 1 
  • Pop, top, and getMin operations are always called on a non-empty stack
  • Push, pop, top, and getMin are called at most 3 * 10^4 times

LeetCode ⭐⭐

Iii. Analysis of Ideas:

If you have some understanding of the characteristics of the stack advanced after out, this problem should not be difficult.

The best way to do this is to borrow a secondary stack, minStack, which is used to fetch the minimum value in the stack.

Algorithm flow:

Push () method:

Every time a new push() value comes in, if <= the top value of the minStack, push() to the minStack together, which updates the minimum value of the stack;

Pop () method:

Determine if the element that pops () out is the top of the minStack (the minimum). If so, pop() the top of the minStack together. This ensures that the minStack element is always the smallest in the stack.

GetMin () method:

Return to the top of the minStack.

MinStack function analysis:

MinStack is equivalent to traversing the stack, removing all ascending numbers, leaving a stack descending from the bottom of the stack to the top. Each time a descending element pops (), minStack pops () the corresponding top element out, ensuring that the top element is always the smallest in the stack.

Animation demo:

Iv. Algorithm implementation:

AC code

The specific algorithm code is as follows:

class MinStack { Deque<Integer> xStack; Deque<Integer> minStack; public MinStack() { xStack = new LinkedList<Integer>(); minStack = new LinkedList<Integer>(); minStack.push(Integer.MAX_VALUE); } public void push(int x) { xStack.push(x); minStack.push(Math.min(minStack.peek(), x)); } public void pop() { xStack.pop(); minStack.pop(); } public int top() { return xStack.peek(); } public int getMin() { return minStack.peek(); }}Copy the code

V. Summary:

The screenshot of leetcode submission results is as follows:

Complexity analysis:

  • Time complexity: O(1). The time complexity of pushing, removing, and obtaining the minimum value is O(1).
  • Space complexity: O(n). The auxiliary stack with n elements takes up additional space of linear size.

A stack of xStack is used to store data, and a stack of minStack is used to store the smallest value in the stack. Pa, over the thing, do not know the small partners have comprehended its mystery.

If you have any better ideas or ideas, please let me know in the comments section. We can learn from each other and grow faster.

Well, that’s all for this episode and I’ll see you next time.

Six, the previous recommendation:

  • Leetcode -1. Sum of two numbers
  • Leetcode – 9. Palindrome
  • Leetcode -13. Roman numeral to integer
  • Leetcode -14. The longest public prefix
  • Leetcode -20. Valid parentheses
  • Leetcode -21. Merge two ordered lists
  • Leetcode -26. Remove duplicates from ordered arrays

Vii. End of article:

If you want to learn more, check out bug Bug’s LeetCode Problem of the Day column! With you brush together, each column is attached with a detailed solution, hand in hand with you to solve the problem.

One person may feel very tired and difficult to persist in brushing, but a group of people will think it is a meaningful thing to brush, urge and encourage each other, and become stronger together.

I am bug fungus, a want to go 👣 out of the mountain to change the fate of the program ape. The next road is still very long, waiting for us to break through, to challenge. Come on, friends, let’s come on! Fighting for the future!

Finally, I like to send you two words, and you share!

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

☘️ Be who you want to be, there is no time limit, you can start whenever you want,

🍀 You can change from now on, you can also stay the same, this thing, there are no rules to speak of, you can live the most wonderful yourself.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

​

💌 If this article is helpful to you, please leave a like! (# ^. ^ #);

💝 if you like the article shared by bug fungus, please give bug fungus a point of concern! The danjun ‘ᴗ, you guys will have a cameo appearance with you.

💗 if you have any questions about the article, please also leave a message at the end of the article or add a group [QQ communication group :708072830];

💞 In view of the limited personal experience, all views and technical research points, if you have any objection, please directly reply to participate in the discussion (do not post offensive comments, thank you);

💕 copyright notice: original is not easy, reprint please attach the original source link and this article statement, all rights reserved, piracy will investigate!! thank you