min-stack

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the <code>MinStack</code> class:

<ul>
	<li><code>MinStack()</code> initializes the stack object.</li>
	<li><code>void push(int value)</code> pushes the element <code>value</code> onto the stack.</li>
	<li><code>void pop()</code> removes the element on the top of the stack.</li>
	<li><code>int top()</code> gets the top element of the stack.</li>
	<li><code>int getMin()</code> retrieves the minimum element in the stack.</li>
</ul>

You must implement a solution with <code>O(1)</code> time complexity for each function.

&nbsp;
Example 1:

<pre>
Input
[&quot;MinStack&quot;,&quot;push&quot;,&quot;push&quot;,&quot;push&quot;,&quot;getMin&quot;,&quot;pop&quot;,&quot;top&quot;,&quot;getMin&quot;]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
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
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>-231 &lt;= val &lt;= 231 - 1</code></li>
	<li>Methods <code>pop</code>, <code>top</code> and <code>getMin</code> operations will always be called on non-empty stacks.</li>
	<li>At most <code>3 * 104</code> calls will be made to <code>push</code>, <code>pop</code>, <code>top</code>, and <code>getMin</code>.</li>
</ul>

Min Stack

Sliding Window Maximum

sliding-window-maximum

滑动窗口最大值

Max Stack

max-stack

最大栈

Stack

Design

&#35774;&#35745;&#19968;&#20010;&#25903;&#25345; <code>push</code> &#65292;<code>pop</code> &#65292;<code>top</code> &#25805;&#20316;&#65292;&#24182;&#33021;&#22312;&#24120;&#25968;&#26102;&#38388;&#20869;&#26816;&#32034;&#21040;&#26368;&#23567;&#20803;&#32032;&#30340;&#26632;&#12290;

&#23454;&#29616; <code>MinStack</code> &#31867;:

<ul>
	<li><code>MinStack()</code> &#21021;&#22987;&#21270;&#22534;&#26632;&#23545;&#35937;&#12290;</li>
	<li><code>void push(int value)</code> &#23558;&#20803;&#32032; <code>value</code> &#25512;&#20837;&#22534;&#26632;&#12290;</li>
	<li><code>void pop()</code> &#21024;&#38500;&#22534;&#26632;&#39030;&#37096;&#30340;&#20803;&#32032;&#12290;</li>
	<li><code>int top()</code> &#33719;&#21462;&#22534;&#26632;&#39030;&#37096;&#30340;&#20803;&#32032;&#12290;</li>
	<li><code>int getMin()</code> &#33719;&#21462;&#22534;&#26632;&#20013;&#30340;&#26368;&#23567;&#20803;&#32032;&#12290;</li>
</ul>

&nbsp;

&#31034;&#20363; 1:

<pre>
&#36755;&#20837;&#65306;
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

&#36755;&#20986;&#65306;
[null,null,null,null,-3,null,0,-2]

&#35299;&#37322;&#65306;
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --&gt; &#36820;&#22238; -3.
minStack.pop();
minStack.top(); --&gt; &#36820;&#22238; 0.
minStack.getMin(); --&gt; &#36820;&#22238; -2.
</pre>

&nbsp;

&#25552;&#31034;&#65306;

<ul>
	<li><code>-231&nbsp;&lt;= val &lt;= 231&nbsp;- 1</code></li>
	<li><code>pop</code>&#12289;<code>top</code> &#21644; <code>getMin</code> &#25805;&#20316;&#24635;&#26159;&#22312; &#38750;&#31354;&#26632; &#19978;&#35843;&#29992;</li>
	<li><code>push</code>,&nbsp;<code>pop</code>,&nbsp;<code>top</code>, and&nbsp;<code>getMin</code>&#26368;&#22810;&#34987;&#35843;&#29992;&nbsp;<code>3 * 104</code>&nbsp;&#27425;</li>
</ul>

Sunbelt Computer Software

PL/B Language Development and Support