1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
示例：
输入："abbaca"
输出："ca"
方法：使用栈
类似于判断括号序列是否有效，使用栈存储遍历过程中的字符，如果当前字符和栈顶相同，则出栈。
public String removeDuplicates(String s) {
Deque<Character> stack = new LinkedList<>();
for (char c : s.toCharArray()) {
if (!stack.isEmpty() && stack.peek() == c)
stack.pop();
else
stack.push(c);
}
StringBuilder builder = new StringBuilder();
for (char c : stack) {
builder.append(c);
}
return builder.reverse().toString();
}
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
分析：需要在常数时间内找到最小元素，所以需要借助额外的空间来存储最小元素信息。具体来说，在存储所有元素的栈之外，使用另一个栈来存储对应于每个元素位置的最小元素。
在每次 push 操作中，除了将元素压入 stack ，还要比较该元素和 min_stack 栈顶元素的大小，将较小者压入 min_stack 栈。然后在每次 pop 操作中，需要将两个栈的栈顶元素同步弹出。这样每次找最小元素时，直接将 min_stack 栈顶元素弹出即可。
在 Java 中，使用 Deque 接口来实现栈结构，具体实现类为 LinkedList 。
class MinStack {
private Deque<Integer> dataStack;
private Deque<Integer> minDataStack;
public MinStack() {
this.dataStack = new LinkedList<>();
this.minDataStack = new LinkedList<>();
minDataStack.push(Integer.MAX_VALUE);
}
public void push(int val) {
this.dataStack.push(val);
int minData = this.minDataStack.peek();
this.minDataStack.push(val < minData ? val : minData);
}
public void pop() {
this.dataStack.pop();
this.minDataStack.pop();
}
public int top() {
return this.dataStack.peek();
}
public int getMin() {
return this.minDataStack.peek();
}
}
239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回每个窗口的最大值 。
方法一：优先队列
用优先队列实现一个大根堆，初始状态下，将数组的前 k 个元素放入堆中，然后向右移动窗口，不断将新元素放入队列。每加入一个新元素，检查当前堆顶元素（最大值）是否还在当前窗口，如果不在，则将其从堆中删除，如果还在，它就是当前窗口的最大值。
为了方便知道堆顶元素是否在当前窗口，在堆中存储每个元素的同时，一并存储各自的索引，即队列中的元素类型为二元组 (num, index)。
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
public int compare(int[] pair1, int[] pair2) {
// 按照数值从大到小排列，数值相同的按照索引从大到小排列
if (pair1[0] != pair2[0]) return pair2[0] - pair1[0];
else return pair2[1] - pair1[1];
}
});
// 将前 k 个元素入队
for (int i = 0; i < k; i++) {
queue.offer(new int[]{nums[i], i});
}
// 滑动窗口
int[] result = new int[n-k+1];
result[0] = queue.peek()[0];
for (int i = k, j = 1; i < n; i++, j++) {
queue.offer(new int[]{nums[i], i});
while (queue.peek()[1] <= i - k) queue.poll();
result[j] = queue.peek()[0]; // 堆顶元素加入结果
}
return result;
}
方法二：单调队列
遍历每个元素，对于当前元素 nums[i] ：
- 首先将队尾中所有不大于
nums[i]的元素所在位置删除（因为这些被删除的元素肯定不是当前窗口的最大值）； - 然后将当前元素所在位置
i入队，此时：- 队头元素如果在当前窗口，那它就是当前窗口的最大值；
- 否则，将不在当前窗口的队头元素删除，最后剩下的队头元素就是当前窗口的最大值。
队列中保存的索引所对应的元素值，从队头到队尾是递减的，所以叫做单调队列。
因为在单调队列中添加元素时需要从队尾删除元素，而在确定当前窗口的最大值时需要从队头删除元素，所以需要使用双端队列。
// 双端队列：
// --------------------
// 队尾 x x x x x x 队头
// --------------------
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new LinkedList<>();
int n = nums.length;
int[] result = new int[n-k+1];
// 将前 k 个元素入队
for (int i = 0; i < k; i++) {
// 将队尾不大于当前元素的删除
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
}
result[0] = nums[deque.peekFirst()];
// 遍历后续 n-k 个元素
for (int i = k, j = 1; i < n; i++, j++) {
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
// 将不在当前窗口的队头元素删除
while (deque.peekFirst() <= i - k) deque.pollFirst();
result[j] = nums[deque.peekFirst()];
}
return result;
}
347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
按 任意顺序 返回 k 个频率最大的元素，就是在暗示使用 堆 来做。
那么使用大根堆还是小根堆呢？
维护一个大小为 k 的小根堆，那么堆顶元素就是当前堆中的最小元素，当堆中元素满了之后，在加入新元素时：
- 如果新元素不大于堆顶元素，那么直接舍弃；
- 否则将堆顶元素删除，将当前元素加入堆中。
这样一来，堆中保存的始终是目前为止最大的 k 个元素，遍历结束时，堆中的元素就是答案。
public int[] topKFrequent(int[] nums, int k) {
// 统计出现次数
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) +1);
}
// 元素以 (num, frequency) 形式的二元组存储
PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[1] - b[1]; // 排序靠前的优先级高（先出队）
}
});
// 遍历 map 建堆
int n = nums.length;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
if (queue.size() < k) {
queue.offer(new int[]{num, count});
} else if (queue.size() == k){
if (queue.peek()[1] < count) {
queue.poll();
queue.offer(new int[]{num, count});
}
}
}
// 堆中的元素就是答案
int[] result = new int[k];
int i = 0;
while (!queue.isEmpty()) {
result[i++] = queue.poll()[0];
}
return result;
}