队列和栈
- 队列实现栈、栈实现队列
- 单调栈
- 单调队列
- 运用栈去重
图片来源于网络
1. 队列实现栈、栈实现队列
队列是一种先进先出的数据结构，栈是一种先进后出的数据结构。
1.1 用栈实现队列
队列的 API 如下：
class MyQueue {
// 添加元素到队尾
public void push(int x);
// 删除队头的元素并返回
public int pop();
// 返回队头元素
public int peek();
// 判断队列是否为空
public boolean empty();
}
用栈实现队列思路是：使用两个栈 s1、 s2，当调用 push 让元素入队时，只要把元素压入 s1，当 s2 为空时，可以把s1 的所有元素取出再添加进 s2，此时s2 中元素就是 先进先出 的顺序了。
public class MyQueue {
// 两个栈 s1、s2
private final Stack<Integer> s1, s2;
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
/**
* 添加元素到队尾
*/
public void push(int x) {
s1.push(x);
}
/**
* 删除队头的元素并返回
*/
public int pop() {
// 先调用 peek 保证 s2 非空
peek();
return s2.pop();
}
/**
* 返回队头元素
*/
public int peek() {
if (s2.isEmpty()) {
// 把 s1 元素压入 s2
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
return s2.peek();
}
/**
* 判断队列是否为空
*/
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
值得注意的是，上述调用 peek 操作时可能触发 while 循环，这样时间复杂度是 O(N) （最坏情况），但大部分情况下 while 循环不会被触发，即其均摊时间复杂度是 O(1)。
1.2 用队列实现栈
栈的 API 如下：
class MyStack {
// 添加元素到栈顶
public void push(int x);
// 删除栈顶的元素并返回
public int pop();
// 返回栈顶元素
public int top();
// 判断栈是否为空
public boolean empty();
}
之前用双栈实现队列比较巧妙，而用队列实现栈就相对简单了，只需要一个队列作为底层数据结构。
public class MyStack {
Queue<Integer> q = new LinkedList<>();
int top_elem = 0;
/**
* 添加元素到栈顶
*
* 直接将元素加入队列，同时记录队尾元素
*/
public void push(int x) {
// x 是队列的队尾，是栈的栈顶
q.offer(x);
top_elem = x;
}
/**
* 删除栈顶的元素并返回
*
* 底层数据结构是先进先出的队列，每次pop只能从队头取元素；
* 但是栈是后进先出，也就是说popAPI 要从队尾取元素
* 把队列前面的都取出来再加入队尾，让之前的队尾元素排到队头，这样就可以取出了
*/
public int pop() {
int size = q.size();
// 留下队尾 2 个元素
while (size > 2){
q.offer(q.poll());
size--;
}
// 记录新的队尾元素
top_elem = q.peek();
q.offer(q.poll());
// 之前的队尾元素已经到了队头, 删除之前的队尾元素
return q.poll();
}
/**
* 返回栈顶元素
*/
public int top() {
return top_elem;
}
/**
* 判断栈是否为空
*/
public boolean empty() {
return q.isEmpty();
}
}
上面用队列实现栈，pop 操作时间复杂度是 O(N)，其他操作都是 O(1)。
2. 单调栈
单调栈是指每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。
2.1 下一个更大元素 I
/**
* 下一个更大元素 I
* <p>
* 给你一个数组，返回一个等长的数组，对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1
* <p>
* 比如，输入一个数组nums = [2,1,2,4,3]，你返回数组[4,2,4,-1,-1]
* <p>
* 若用暴力解法对每个元素都进行扫描，时间复杂度是O(n^2)）
* <p>
* 时间复杂度：看着像是 O(n^2)，其实是 O(n)
*/
private int[] nextGreaterElement(int[] nums) {
int[] res = new int[nums.length]; // 存放数组的答案
Stack<Integer> s = new Stack<>();
// 倒着往栈里放
for (int i = nums.length - 1; i >= 0; i--) {
// 元素大小想象成人的身高
// 判定个子高矮
while (!s.empty() && s.peek() <= nums[i]) {
// 矮个起开，反正也被挡着了。。。
s.pop();
}
// num[i] 后面的 next great number
res[i] = s.empty() ? -1 : s.peek();
s.push(nums[i]);
}
return res;
}
上面就是单调队列解决问题的模板：
for 循环要从后往前扫描元素，因为借助的是栈的结构，倒着入栈，其实是正着出栈。
while 循环是把两个「个子高」元素之间的元素排除，因为他们的存在没有意义，前面挡着个「更高」的元素。
上述问题可以简单变形为力扣第 1118 题「一月有多少天」：
/**
* 一月有多少天
* <p>
* 给你一个数组T，这个数组存放的是近几天的天气气温，你返回一个等长的数组，
* 计算：对于每一天，你还要至少等多少天才能等到一个更暖和的气温；如果等不到那一天，填 0
* <p>
* 比如说给你输入T = [73,74,75,71,69,76]，你返回[1,1,3,2,1,0]
* <p>
* 这个问题本质上也是找 Next Greater Number，只不过现在不是问你 Next Greater Number 是多少，
* 而是问你当前距离 Next Greater Number 的距离而已
*/
private int[] dailyTemperatures(int[] nums) {
int[] res = new int[nums.length];
Stack<Integer> s = new Stack<>(); // 这边存元素索引
// 单调栈模板
for (int i = nums.length - 1; i >= 0; i--) {
while (!s.empty() && nums[s.peek()] <= nums[i]) {
s.pop();
}
// 得到索引间距
res[i] = s.empty() ? 0 : (s.peek() - i);
// 将索引入栈，而不是元素
s.push(i);
}
return res;
}
2.1 下一个更大元素 II：循环数组
/**
* 下一个更大元素 II：循环数组
* <p>
* 假设给你的数组是个环形的，比如输入一个数组[2,1,2,4,3]，你返回数组[4,2,4,-1,4]。
* 拥有了环形属性，最后一个元素 3 绕了一圈后找到了比自己大的元素 4。
* <p>
* 对于这种需求，常用套路就是将数组长度翻倍：
* 可以不用构造新数组，而是利用循环数组的技巧来模拟数组长度翻倍的效果。
* <p>
* 时间复杂度O(N)
*/
private int[] nextGreatElements(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Stack<Integer> s = new Stack<>();
// 假设这个数组长度翻倍了
for (int i = 2 * n - 1; i >= 0; i--) {
// 索引求模，其他和模板一样
while (!s.empty() && s.peek() <= nums[i % n]) {
s.pop();
}
res[i % n] = s.empty() ? -1 : s.peek();
s.push(nums[i % n]);
}
return res;
}
上述情况，可以把这个双倍长度的数组构造出来，然后套用算法模板。当然也可以不用构造新数组，而是利用循环数组的技巧来模拟数组长度翻倍的效果。
2. 单调队列
单调队列是指队列中的元素全都是单调递增（或递减）的。
单调栈主要解决 下一个更大元素 一类算法问题，而单调队列这个数据结构可以解决滑动窗口问题。
单调队列的实现如下：
/**
* 单调队列
*/
class MonotonicQueue {
// 双链表，支持头部和尾部增删元素
private final LinkedList<Integer> q = new LinkedList<>();
// 在队尾添加元素 n
void push(int n) {
// 将前面小于自己的元素都删除
while (!q.isEmpty() && q.getLast() < n) {
q.pollLast();
}
q.addLast(n);
}
// 返回当前队列中的最大值
int max() {
// 队头的元素肯定是最大的
return q.getFirst();
}
// 队头元素如果是 n，删除它
void pop(int n) {
if (n == q.getFirst()) {
q.pollFirst();
}
}
}
有了上面的单调队列后，就可以处理滑动窗口最大值：
/**
* 滑动窗口最大值
* <p>
* 给你输入一个数组nums和一个正整数k，有一个大小为k的窗口在nums上从左至右滑动，请你输出每次窗口中k个元素的最大值
* <p>
* 如：输入 nums=[1,3,-1,-3,5,3,6,7] 和 k=3，输出 [3,3,5,5,6,7]
* <p>
* 滑动窗口的位置 最大值
*【1 3 -1】-3 5 3 6 7 3
* 1【3 -1 -3】5 3 6 7 3
* 1 3【-1 -3 5】3 6 7 5
* 1 3 -1【-3 5 3】6 7 5
* 1 3 -1 -3【5 3 6】7 6
* 1 3 -1 -3 5【3 6 7】 7
* <p>
* 单调队列：队列中的元素全都是单调递增（或递减）的
*/
private int[] maxSlidingWindow(int[] nums, int k) {
MonotonicQueue window = new MonotonicQueue();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i < k - 1) {
// 先把窗口的前 k - 1 填满
window.push(nums[i]);
} else {
// 窗口开始向前滑动
// 移入新元素
window.push(nums[i]);
// 将当前窗口中的最大元素记入结果
res.add(window.max());
// 移出最后的元素
window.pop(nums[i - k + 1]);
}
}
// 将 List 类型转化成 int[] 数组作为返回值
int[] arr = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
arr[i] = res.get(i);
}
return arr;
}
值得注意的是：在实现 MonotonicQueue 时，使用了 Java 的LinkedList，因为链表结构支持在头部和尾部快速增删元素；而在解法代码中的 res 则使用的 ArrayLis t结构，因为后续会按照索引取元素，所以数组结构更合适。
上述算法中整体的时间复杂度是 O(N)，空间复杂度是窗口的大小 O(k)。
4. 运用栈去重
关于去重算法，前面文章有介绍过有序数组链表的去重使用双指针的快慢指针技巧处理，而力扣第 316 题「去除重复字母」，难度就比较大了，题目如下：
力扣第 316 题 去除重复字母
要求总结出来有三点：
- 要去重。
- 去重字符串中的字符顺序不能打乱s中字符出现的相对顺序。
- 在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果。
先忽略最后一个要求，用「栈」来实现一下前面两个要求：
/**
* 去除重复字母
* <p>
* 给一个仅包含小写字母的字符串，去除重复字母，使得每个字母只出现移除。需保证返回结果的字典序最小
* 要求不能打乱其他字符的相对位置
* <p>
* 如："bcabc" --> "abc", "cbacdcbc" --> "acdb"
* <p>
* 要求一、要去重。
* <p>
* 要求二、去重字符串中的字符顺序不能打乱s中字符出现的相对顺序。
*/
private String removeDuplicateLetters(String s) {
// 存放去重的结果
Stack<Character> stk = new Stack<>();
// 布尔数组初始值为 false，记录栈中是否存在某个字符
// 输入字符均为 ASCII 字符，所以大小 256 够用了
boolean[] inStack = new boolean[256];
for (char c : s.toCharArray()) {
// 如果字符 c 存在栈中，直接跳过
if (inStack[c]) continue;
// 若不存在，则插入栈顶并标记为存在
stk.push(c);
inStack[c] = true;
}
StringBuilder sb = new StringBuilder();
while (!stk.empty()) {
sb.append(stk.pop());
}
// 栈中元素插入顺序是反的，需要 reverse 一下
return sb.reverse().toString();
}
上述代码就是用布尔数组 inStack 记录栈中元素，达到去重的目的，此时栈中的元素都是没有重复的。
接下来处理最后一个要求：
/**
* 去除重复字母
* <p>
* 要求三、在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果。
*/
private String removeDuplicateLetters2(String s) {
Stack<Character> stk = new Stack<>();
boolean[] inStack = new boolean[256];
for (char c : s.toCharArray()) {
if (inStack[c]) continue;
// 插入之前，和之前的元素比较一下大小
// 如果字典序比前面的小，pop 前面的元素
while (!stk.empty() && stk.peek() > c) {
// 弹出栈顶元素，并把该元素标记为不在栈中
inStack[stk.pop()] = false;
}
stk.push(c);
inStack[c] = true;
}
StringBuilder sb = new StringBuilder();
while (!stk.empty()) {
sb.append(stk.pop());
}
// 栈中元素插入顺序是反的，需要 reverse 一下
return sb.reverse().toString();
}
上述代码就是插入了一个 while 循环，连续 pop 出比当前字符小的栈顶字符，直到栈顶元素比当前元素的字典序还小为止。
这样通过「栈」这种顺序结构的 push/pop 操作记录结果字符串，保证了字符出现的顺序和s中出现的顺序一致。
但还有个问题，上面算法在 stk.peek() > c 时才会 pop 元素，这时候应该分两种情况：
- 若
stk.peek()这个字符之后还会出现，那么可以把它pop出去，后面再push到栈里，符合字典序的要求。 - 若
stk.peek()这个字符之后不会出现，栈中不会存在重复的元素，那么就不能把它pop出去，否则就会丢失这个字符。
继续修改如下：
/**
* 去除重复字母
* <p>
* 要求三、在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果。
* <p>
* 时间空间复杂度都是 O(N)
*/
private String removeDuplicateLetters3(String s) {
Stack<Character> stk = new Stack<>();
// 维护一个计数器记录字符串中字符的数量
int[] count = new int[256];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i)]++;
}
boolean[] inStack = new boolean[256];
for (char c : s.toCharArray()) {
// 每遍历过一个字符，都将对应的计数减一
count[c]--;
if (inStack[c]) continue;
while (!stk.empty() && stk.peek() > c) {
// 若之后不存在栈顶元素了，则停止 pop
if (count[stk.peek()] == 0) {
break;
}
// 若之后还有，则可以 pop
inStack[stk.pop()] = false;
}
stk.push(c);
inStack[c] = true;
}
StringBuilder sb = new StringBuilder();
while (!stk.empty()) {
sb.append(stk.pop());
}
return sb.reverse().toString();
}
上述代码用了一个计数器 count，当字典序较小的字符试图「挤掉」栈顶元素时，在 count 中检查栈顶元素是否是唯一，只有当后面还存在栈顶元素时才能挤掉，否则不能挤掉。
这种用类似单调栈的思路，配合计数器count 不断 pop 掉不符合最小字典序的字符，保证了最终得到的结果字典序最小。
参考链接：
