{"id":8870,"date":"2021-11-28T14:01:10","date_gmt":"2021-11-28T22:01:10","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8870"},"modified":"2021-11-28T14:05:40","modified_gmt":"2021-11-28T22:05:40","slug":"leetcode-155-min-stack","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/stack\/leetcode-155-min-stack\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 155. Min Stack"},"content":{"rendered":"\n<p>Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.<\/p>\n\n\n\n<p>Implement the&nbsp;<code>MinStack<\/code>&nbsp;class:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>MinStack()<\/code>&nbsp;initializes the stack object.<\/li><li><code>void push(int val)<\/code>&nbsp;pushes the element&nbsp;<code>val<\/code>&nbsp;onto the stack.<\/li><li><code>void pop()<\/code>&nbsp;removes the element on the top of the stack.<\/li><li><code>int top()<\/code>&nbsp;gets the top element of the stack.<\/li><li><code>int getMin()<\/code>&nbsp;retrieves the minimum element in the stack.<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input<\/strong>\n[\"MinStack\",\"push\",\"push\",\"push\",\"getMin\",\"pop\",\"top\",\"getMin\"]\n[[],[-2],[0],[-3],[],[],[],[]]\n\n<strong>Output<\/strong>\n<\/pre>\n\n\n<p>[null,null,null,null,-3,null,0,-2]<\/p>\n\n\n\n<p><strong>Explanation<\/strong> 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<\/p>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>-2<sup>31<\/sup>&nbsp;&lt;= val &lt;= 2<sup>31<\/sup>&nbsp;- 1<\/code><\/li><li>Methods&nbsp;<code>pop<\/code>,&nbsp;<code>top<\/code>&nbsp;and&nbsp;<code>getMin<\/code>&nbsp;operations will always be called on&nbsp;<strong>non-empty<\/strong>&nbsp;stacks.<\/li><li>At most&nbsp;<code>3 * 10<sup>4<\/sup><\/code>&nbsp;calls will be made to&nbsp;<code>push<\/code>,&nbsp;<code>pop<\/code>,&nbsp;<code>top<\/code>, and&nbsp;<code>getMin<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Two Stack<\/strong>s<\/h2>\n\n\n\n<p>One normal stack, one monotonic stack to store the min values.<\/p>\n\n\n\n<p>Time complexity: O(1) per op<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass MinStack {\npublic:\n  void push(int x) {\n    m_data.push(x);\n    if (m_s.empty() || x <= m_s.top())\n      m_s.push(x);\n  }\n\n  void pop() {\n    if (!m_s.empty() &#038;&#038; m_data.top() == m_s.top())\n      m_s.pop();\n    m_data.pop();\n  }\n\n  int top() {\n    return m_data.top();\n  }\n\n  int getMin() {\n    return m_s.empty() ? m_data.top() : m_s.top();\n  }\nprivate:\n  stack<int> m_data;\n  stack<int> m_s;\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the&nbsp;MinStack&nbsp;class: MinStack()&nbsp;initializes the stack object. void push(int val)&nbsp;pushes&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[407],"tags":[291,222,180],"class_list":["post-8870","post","type-post","status-publish","format-standard","hentry","category-stack","tag-data-structure","tag-easy","tag-stack","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8870","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8870"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8870\/revisions"}],"predecessor-version":[{"id":8872,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8870\/revisions\/8872"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8870"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8870"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8870"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}