单调栈——包含min函数的栈

牛客BM43：包含min函数的栈

---

题目

• 要求：实现栈的push、pop、top、min函数。
• 访问每一个函数的时间复杂度为O(1)。
• 推荐方法：利用双栈。

---

思路

我们都知道栈结构的push、pop、top操作都是O(1)，但是min函数做不到，于是想到在push的时候就将最小值记录下来，由于栈先进后出的特殊性；我们可以构造一个单调栈，保证栈内元素都是递增的，栈顶元素就是当前最小的元素。

---

解题步骤：

• 1、使用一个栈记录进入栈的元素，正常进行push、pop、top操作。
• 2、使用另一个栈记录每一次push入栈的元素的最小值。
• 3、每次push元素都需要和第二个栈的栈顶元素进行比较，若是较小元素，则入第二个栈，若为较大值，则在第二个栈的栈顶元素再次入栈。

---

代码

import java.util.*;
import java.util.Stack;

public class Solution {
    //用于栈的push和pop
    Stack<Integer> s1 = new Stack<>();
    //存储最小min
    Stack<Integer> s2 = new Stack<>();
    
    public void push(int node) {
        s1.push(node);
        //空或者新的元素比较小，则入栈
        if (s2.isEmpty() || s2.peek() > node) {
            s2.push(node);
        } else {
            //重复加入栈顶
            s2.push(s2.peek());
        }
    }
    
    public void pop() {
        s1.pop();
        s2.pop();
    }
    
    public int top() {
        return s1.peek();
    }
    
    public int min() {
        return s2.peek();
    }
}
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

总结

涉及单调栈，请见每日温度——单调栈解法。

单调栈本质就是时间换空间，在遍历的过程中需要一个栈记录右边第一个比当前元素高的数值，优点是只需要遍历一次即可。

利用单调栈需要明确：

1. 单调栈存放的元素是什么？
   单调栈只需要存放元素下标即可，若需要使用对应的元素，则直接A[i]数组形式就可以获取。
2. 单调栈的元素是递增？还是递减？
   注意一下顺序为 从栈头到栈底的顺序。这里使用递增顺序，指的是从栈头到栈底的顺序，只有在递增时，加入一个元素i，才会清楚栈顶元素在数组中右面第一个比栈顶元素大的元素是i。

• 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况。
• 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况。
• 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况。

---