牛客题解-NC90设计getMin功能的栈

发表于 更新于 分类于 阅读次数：

题目

实现一个特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

输入：

1
[[1,3],[1,2],[1,1],[3],[2],[3]]

输出：

1
[1,2]

Tips：

1
2
3
4
5
有三种操作种类，op1表示push，op2表示pop，op3表示getMin。你需要返回和op3出现次数一样多的数组，表示每次getMin的答案

1<=操作总数<=1000000
-1000000<=每个操作数<=1000000
数据保证没有不合法的操作

思路

分析

该题目重点在于获取当前栈中的min值。

考虑为原栈stack1，新建一个stack2栈用来维持stack1中的最小数。由于栈FILO的特性，只需要保证stack2中的栈顶元素维持在一个最小值水平即可。

实现

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
37
38
39
40
import java.util.*;


public class Solution {
    /**
     * return a array which include all ans for op3
     * @param op int整型二维数组 operator
     * @return int整型一维数组
     */
    public int[] getMinStack (int[][] op) {
        // write code here
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        int flag;
        for(int i = 0; i<op.length; i++){
            flag = op[i][0];
            if(flag == 1){
                s1.push(op[i][1]);
                if(s2.isEmpty() || s2.peek() >= op[i][1]){
                    s2.push(op[i][1]);
                }
            }
            if(flag == 2){
                int value = s1.pop();
                if(value == s2.peek()){
                    s2.pop();
                }
            }
            if(flag == 3){
                list.add(s2.peek());
            }
        }
        int[] res = new int[list.size()];
        for(int j = 0; j<list.size(); j++){
            res[j] = list.get(j);
        }
        return res;
    }
}