Min Stack

Myth丶恋晨 2022-06-09 01:52 140阅读 0赞

LeetCode 155. Min Stack

Difficulty:Easy

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.  
push(x) -- Push element x onto stack.  
pop() -- Removes the element on top of the stack.  
top() -- Get the top element.  
getMin() -- Retrieve the minimum element in the stack.  
Example:  
MinStack minStack = new MinStack();  
minStack.push(-2);  
minStack.push(0);  
minStack.push(-3);  
minStack.getMin(); --> Returns -3.  
minStack.pop();  
minStack.top(); --> Returns 0.  
minStack.getMin(); --> Returns -2.

本题的难点在于当最小值被弹出后，还能输出次小值，因此需要将元素间比较大小的过程均记录下来，而不能仅仅记录最小值，因此记录最小值的过程也采用一个栈来实现，当该栈的最小值被弹出后，次小值成为了最小值。

class MinStack \{  
public:  
/\*\* initialize your data structure here. \*/  
stack<int> s;  
stack<int> sMin;//记录最小值变化过程的栈  
void push(int x) \{  
s.push(x);  
if (sMin.empty() || x <= getMin()) sMin.push(x);  
\}  
  
void pop() \{  
if (s.top() == sMin.top()) sMin.pop();  
s.pop();  
\}  
  
int top() \{  
return s.top();  
\}  
  
int getMin() \{  
return sMin.top();  
\}  
\};

/\*\*  
\* Your MinStack object will be instantiated and called as such:  
\* MinStack obj = new MinStack();  
\* obj.push(x);  
\* obj.pop();  
\* int param\_3 = obj.top();  
\* int param\_4 = obj.getMin();  
\*/

参考Discuss，发现头名使用一个stack完成任务，厉害！

目前没理解，留个坑待填。

\----------------------------------------------------------------------------------------------------------------------------------------------------------

填一下，思路是在min改变时，通过压栈记录之前的min；当min弹栈时，记录值也弹出并赋给min

class MinStack \{  
public:  
/\*\* initialize your data structure here. \*/  
stack<int> s;  
int temp = INT\_MAX;  
void push(int x) \{  
if (x <= temp)  
\{  
s.push(temp);  
temp = x;  
\}  
s.push(x);  
\}  
  
void pop() \{  
if (s.top() == temp)  
\{  
s.pop();  
temp = s.top();  
s.pop();  
\}  
else s.pop();  
\}  
  
int top() \{  
return s.top();  
\}  
  
int getMin() \{  
return temp;  
\}  
\};