代码随想录算法训练营day13 | 题目239、题目347、题目155
题目一描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 | 最大值
[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
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
解题思路
设置一个双端队列，使用单调队列，头部是最大值，尾部比较小。
每次滑动窗口获得新的数据，将其从尾部往前比较，比它小的都移除，直到遇到大于等于这个数的元素停下。
滑动窗口移动移除最左边元素的时候，若是与队列内最大值相等，则同步移除队列内元素。
每次移动的滑动窗口内最大值都是队列头元素。
代码实现
方法一：
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new ArrayDeque<>();
int[] res = new int[nums.length - k + 1];
int index = 0;
for (int i = 0; i < k; i++) {
while (!deque.isEmpty() && nums[i] > deque.peekLast()) {
deque.pollLast();
}
deque.offerLast(nums[i]);
}
res[index++] = deque.peekFirst();
for (int i = k; i < nums.length; i++) {
while (!deque.isEmpty() && nums[i] > deque.peekLast()) {
deque.pollLast();
}
deque.offerLast(nums[i]);
if (nums[i - k] == deque.peekFirst()) {
deque.pollFirst();
}
res[index++] = deque.peekFirst();
}
return res;
}
}
题目二描述
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
1 <= nums.length <= 10^5
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
解题思路
先放入map统计词频，再根据词频排序，返回频率最高的前k个元素。
使用优先级队列的小顶堆，维护一个大小为k的堆，最后得到的结果就是最大的前k个元素。
也可以用选择排序的方法，把有这些频率的词放入下标为频率的数组，空间换时间，由于数组下标有从小到大的隐形排序，直接倒序获得即可。
代码实现
方法一：
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int[] res = new int[k];
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(
// (entry1, entry2) -> (entry1.getValue() - entry2.getValue()));
PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(
(entry1, entry2) -> (entry1.getValue().compareTo(entry2.getValue())));
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
// if(entry.getValue() < heap.peek().getValue()) continue;
// heap.offer(entry);
// if (heap.size() > k) {
// heap.poll();
// }
if (heap.size() < k) {
heap.offer(entry);
} else if (entry.getValue() > heap.peek().getValue()) {
heap.poll();
heap.offer(entry);
}
}
int index = 0;
while (!heap.isEmpty()) {
res[index++] = heap.poll().getKey();
}
return res;
}
}
方法二：
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int[] res = new int[k];
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
ArrayList<Integer>[] frequency = new ArrayList[nums.length + 1];
for (int key : map.keySet()) {
int freq = map.get(key);
if (frequency[freq] == null) {
frequency[freq] = new ArrayList<>();
}
frequency[freq].add(key);
}
int index = 0;
for (int i = frequency.length - 1; i >= 0; i--) {
if (frequency[i] != null) {
for (int num : frequency[i]) {
res[index++] = num;
if (index == res.length) {
return res;
}
}
}
}
return res;
}
}
技巧总结
O(n)是小于O(nlogn)的。
找前k个最大元素，最好用小顶堆，因为小顶堆每次出队列的都是最小的那个元素，维护k的队列长度，最后留下的就是前k个最大元素。
找前k个最小元素，最好用大顶堆，同理。
学会优先级队列的初始化，优先级队列默认是小顶堆
注意最好用compareTo来比较
学会map的遍历方法，子元素数据类型是Map.Entry<?,?>
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {}
与堆顶元素比较并有选择的操作，更有效率。
ArrayList<Integer>[] frequency = new ArrayList[nums.length + 1]; 不会初始化ArrayList，必须显式创建。
题目三描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
-2^31 <= val <= 2^31- 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次
解题思路
维护一个辅助栈，同步记录入栈时候的目前栈内最小值，这样就永远能得到原来栈内的最值了。
代码实现
方法一：
class MinStack {
Deque<Integer> stack;
Deque<Integer> min_stack;
public MinStack() {
stack = new ArrayDeque<>();
min_stack = new ArrayDeque<>();
}
public void push(int val) {
stack.push(val);
if(!min_stack.isEmpty() && min_stack.peek() < val)
min_stack.push(min_stack.peek());
else
min_stack.push(val);
}
public void pop() {
stack.pop();
min_stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min_stack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
技巧总结
注意如果有比较两个Integer相等的情况，要用equals
