【算法方法总结·六】栈队列堆的一些技巧和注意事项

  • 【算法方法总结·一】二分法的一些技巧和注意事项
  • 【算法方法总结·二】双指针的一些技巧和注意事项
  • 【算法方法总结·三】滑动窗口的一些技巧和注意事项
  • 【算法方法总结·四】字符串操作的一些技巧和注意事项
  • 【算法方法总结·五】链表操作的一些技巧和注意事项
  • 【算法方法总结·六】栈队列堆的一些技巧和注意事项 🎯

【栈】

可以用 Stack，但是一般用 Deque，比较方便

Stack

1
2
3
4
5
6
7
8
Stack<Integer> stack = new Stack<>()

stack.pop() // 出栈，并返回出栈元素
stack.push(x) // 把x入栈
stack.peek() // 返回栈顶元素
stack.isEmpty() // 是否为空
stack.isFull() // 是否满了
stack.length // 长度

Deque

也支持 栈操作

1
2
3
4
5
6
7
8
9
// 双端队列
Deque<Integer> deque = new Linkedlist<>()

// 也支持栈操作
pop()：removeFirst()
push()：addFirst()
peek()：peekFirst()
poll()：pollFirst()
offer(x)：offerLast(x)

【单调栈】

  • 通常是一维数组，要寻找==任一个元素的右边或者左边第一个比自己大或者小的元素的位置==，此时我们就要想到可以用单调栈了

  • 单调栈的本质是空间换时间，更直白来说，就是用一个栈来记录我们遍历过的元素

  • 顺序的描述为 从栈头到栈底的顺序

    例如 接雨水问题

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 Solution {
    public int trap(int[] height) {
        Deque<Integer> st = new LinkedList<>(); // 存下标
        int len = height.length;
        st.push(0); // 第一个元素的下标 0 入栈
        int res = 0;
        for (int i = 1; i < len; i++) {
        	// 单调栈的栈顶元素一定是最小的
            if (height[i] < height[st.peek()]) {
                st.push(i);
            } else if (height[i] == height[st.peek()]) { // 顶==添加，用右边的
                st.pop(); // 左边的弹出
                st.push(i);
            } else { // 顶 < 添加，开始计算并出栈
                while (!st.isEmpty() && height[i] > height[st.peek()]) {
                    int mid = st.pop(); // 凹槽
                    if (!st.isEmpty()) {
                        int left = st.peek();
                        // right=i
                        // min（左，右）- 凹槽
                        int h = Math.min(height[i], height[left]) - height[mid];
                        int w = i - left - 1;
                        int hold = h * w;// 当前行接雨量
                        res += hold;
                    }
                }
                st.push(i);
            }
        }
        return res;
    }
}

【队列堆】

普通队列

Queue 是个接口，在实例化时必须实例化 LinkedList 的对象，因为 LinkedList 实现了 Queue 接口

1
2
3
4
5
6
7
Queue<Integer> queue = new LinkedList<>();

queue.size() // 长度
queue.peek() / queue.element() // 返回队头元素
queue.poll() / queue.remove() // 出队，并返回出队元素
queue.offer(x) / queue.add(x) // 入队
queue.isEmpty() //是否为空

双端队列

Deque 是一个接口，使用时必须创建 LinkedList 的对象（一般不用 ArrayDeque），它也支持 Queue的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

// 其方法相对于 Queue 多了 -First 及 -Last
addFirst() / offerFirst()
removeFirst() / pollFirst()
getFirst() / peekFirst()

// 也支持栈操作
pop()：removeFirst()
push()：addFirst()
peek()：peekFirst()
poll()：pollFirst()
offer(x)：offerLast(x)

优先队列【即为堆】

PriorityQueue 默认情况下是小根堆 —— 即每次获取到的元素都是最小的元素

1
2
// 默认为小根堆
PriorityQueue<Integer> q1 = new PriorityQueue<>();

3 种 大根堆 自定义方式

方法一

1
2
3
4
5
6
7
8
9
// 大根堆要自己定义
// 定义方式(1)
class IntCmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}
PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());

方法二

1
2
3
4
5
6
// 定义方式(2)
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
	public int compare(int[] o1, int[] o2) {
		return o2[1] - o1[1];
	}
});

方法三：Lambda 表达式 （推荐）

1
2
// 定义方式(3) Lambda表达式--推荐
PriorityQueue<int[]> p = new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);

堆操作

1
2
3
4
5
6
size() // 有效元素个数
offer() / add() // 插入
peek() // 获取优先级最高的元素
poll() / remove() // 移除优先级最高的元素
clear() // 清空
isEmpty() // 是否为空

相关力扣题

  • 相关解法见【算法题解答·六】栈队列堆

232.用栈实现队列

150. 逆波兰表达式求值

239. 滑动窗口最大值

347.前 K 个高频元素

20.有效的括号

155.最小栈

394.字符串解码

739.每日温度

84.柱状图中最大的矩形

215.数组中的第k个最大元素

295.数据流的中位数