LeetCode 30 days Challenge - Day 10

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

Min Stack

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.

Solution

题目要求分析：实现一个最小栈，包括压栈、退栈、返回最小值等函数。

解法：

最小栈结构为了记录最小值，需要多使用一个栈来记录最小值。

接下来，讨论各个方法如何实现：

push() 压栈：
1. 首先，无论如何将数据压入数据栈；
2. 接着进行判断，若最小栈栈顶元素大于或等于压入的数据，将该数据压入最小栈。
  
  （此处注意，等于的情况也要压栈，这样才能避免退栈操作在多个最小值删除。）
pop() 出栈：
1. 首先，若最小栈栈顶元素等于当前栈顶元素，将最小栈栈顶元素弹出。
  
  （此处注意push操作中第二步的注释。）
2. 将栈顶元素出栈。
top() 访问栈顶元素：调用vector结构的back()方法。
getMin() 访问最小值：调用stack结构的top()方法。

class MinStack {
public:
    stack<int> ministack;
    vector<int> v;
    
    MinStack() {
        ministack.push(INT_MAX);
    }
    
    void push(int x) {
        v.push_back(x);
        if (x <= ministack.top()) ministack.push(x);
    }
    
    void pop() {
        if (v.back() == ministack.top()) ministack.pop();
        v.pop_back();
    }
    
    int top() {
        return v.back();
    }
    
    int getMin() {
        return ministack.top();
    }
};

传送门：Min Stack

Karl

Karl's Nest

leetcode-day-10

LeetCode 30 days Challenge - Day 10

Min Stack

Solution