【leetcode】155：Min Stack

Posted on

最小栈

难度：Easy

题目描述

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

  • push(x) – 将元素 x 推入栈中。
  • pop() – 删除栈顶的元素。
  • top() – 获取栈顶元素。
  • getMin() – 检索（retrievie）栈中的最小元素。

示例

1
2
3
4
5
6
7
8
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.

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {}
    
    void push(int x) {
        s1.push(x);
        if (s2.empty() || x <= s2.top()) s2.push(x);
    }
    
    void pop() {
        if (s1.top() == s2.top()) s2.pop();
        s1.pop();
    }
    
    int top() {
        return s1.top();
    }
    
    int getMin() {
        return s2.top();
    }
    
private:
    stack<int> s1, s2;
};

思路

用两个栈，s1来按顺序存储push进来的数据，s2的栈顶用来存最小值

知识点

stack(堆栈）是一个容器的改编，它实现了一个先进后出的数据结构（FILO）。
定义stack对象的示例如下：

1
2
stack<int> s1;
stack<string> s2;

stack的基本操作如下：

函数名 功能 复杂度
size() 返回栈的元素数 O(1)
top() 返回栈顶的元素 O(1)
pop() 从栈中取出并删除元素 O(1)
push(x) 向栈中添加元素x O(1)
empty() 在栈为空时返回true O(1)

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        min_val = INT_MAX;
    }
    
    void push(int x) {
        if (x <= min_val) {
            st.push(min_val);
            min_val = x;
        }
        st.push(x);
    }
    
    void pop() {
        int t = st.top(); st.pop();
        if (t == min_val) {
            min_val = st.top(); st.pop();
        }
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return min_val;
    }
private:
    int min_val;
    stack<int> st;
};

知识点

常量INT_MAX 表示最大整数 2^31-1，INT_MIN表示最小整数-2^31