LeetCode155-最小栈

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/min-stack/

中文链接：https://leetcode-cn.com/problems/min-stack/

题目详述

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

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

示例:

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

题目详解

方法一：运用两个栈。

  • numStack 用来记录数据，minStack 用来记录最小值。
  • push 元素时，numStack 直接 push；minStack 在为空或当前元素小于等于栈顶元素的时侯才 push。
  • pop 元素时，numStack 直接 push；若弹出元素等于 minStack 栈顶元素，minStack 也需要 pop。
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
34
35
36
public class LeetCode_00155 {

    // 运用两个栈
    class MinStack {
        private Stack<Integer> numStack;
        private Stack<Integer> minStack;

        /** initialize your data structure here. */
        public MinStack() {
            numStack = new Stack<>();
            minStack = new Stack<>();
        }

        public void push(int x) {
            numStack.push(x);
            if (minStack.isEmpty() || x <= minStack.peek()) {
                minStack.push(x);
            }
        }

        public void pop() {
            int x = numStack.pop();
            if (x == minStack.peek()) {
                minStack.pop();
            }
        }

        public int top() {
            return numStack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }
}

方法二：运用一个栈 + 一个变量。

  • stack 用来记录数据，min用来记录当前最小值。
  • push 元素时，若当前元素小于等于 min，需要 push 一次 min，并更新 min，再 push 当前元素；否则直接 push 当前元素。
  • pop 元素时，弹出栈顶元素，若弹出元素等于 min，还需要额外再 pop 一次赋值给 min。
  • 这种做法相当于每次把最小元素和次小元素缓存起来，每次 pop 时，可以得到下一次的最小值。
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
34
35
36
public class LeetCode_00155 {

    // 运用一个栈 + 一个变量
    class MinStack {
        private Stack<Integer> stack;
        private int min;

        /** initialize your data structure here. */
        public MinStack() {
            stack = new Stack<>();
            min = Integer.MAX_VALUE;
        }

        public void push(int x) {
            if (x <= min) {
                stack.push(min);
                min = x;
            }
            stack.push(x);
        }

        public void pop() {
            if (min == stack.pop()) {
                min = stack.pop();
            }
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return min;
        }
    }
}