● 239. 滑动窗口最大值
● 347.前 K 个高频元素
● 总结
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//思路:遍历数组,连个指针(快慢指针),快指针用作遍历(每次加1),慢指针用作下标(每次加k)
//取到一组后放进一个数组里面,取出最大值,然后放进队列中
//最终队列出列,放进数组里面返回
//看完代码随想录后的思路
//定义一个队列,我们自己去自定义方法
//遍历前k个,先将数组前k个加入到队列中
//(如果是队列为空就直接加进去,如果不为空并且要加入的目标值大于队列顶部的值,那么我们就先将这个顶部的值出列,然后我们再将目标值加入进去,保证栈顶元素是最大的)
//然后将这个栈顶元素保存下来,这个就是第一个滑动窗口的最大值了
//然后我们进行下一轮窗口的判断,如果此时栈顶元素等于我们的上一轮滑动窗口的第一个元素,那么我们需要将他移除(当然也有可能跟在第一轮滑动窗口处理就被因为小被挤出去了)
//再将这个下一轮窗口的最后一个元素加入进去队列
//最后再次取出这个队列的栈顶元素,也就是最大值保存起来
//当数组长度为1时,直接返回该数组
if(nums.length==1){
return nums;
}
//创建存放结果的数组
int[] arr=new int[nums.length-k+1];
//计数器
int num=0;
//创建自定义队列
MyQueue myqueue=new MyQueue();
//先将前面k个元素放进队列中
for(int i=0;i<k;i++){
myqueue.add(nums[i]);
}
//此时栈顶元素就是此次滑动窗口的最大值
arr[num++]=myqueue.peek();
//将保存值得数组指针往下跳一位
//继续处理剩下得滑动窗口
for(int i=k;i<nums.length;i++){
//先去判断用不用将上一轮滑动窗口的首元素删除
myqueue.poll(nums[i-k]);
//再将下一轮滑动窗口的最后一个元素加进队列中
myqueue.add(nums[i]);
//将栈顶元素保存起来到数组中
arr[num++]=myqueue.peek();
//num++;
}
return arr;
}
}
//自定义队列方法
class MyQueue{
//定义一个队列
Deque<Integer> deque=new LinkedList<>();
//自定义我们想要的增加元素和删除元素的方法
void poll(int val){
//如果此时传进来的目标值等于我们的栈顶元素,我们就将他给移除掉(也就是处理上一轮滑动窗口的第一个元素,才好添加下一轮滑动窗口的最后一个元素进入队列)
if(!deque.isEmpty()&&deque.peek()==val){
deque.poll();
}
}
void add(int val){
//如果添加进来的目标值大于现在队列的最后一个元素,那么我们就先将前面的删除掉再加入进来
while(!deque.isEmpty()&&deque.getLast()<val){
deque.removeLast();//这里的方法都能够看出要去熟悉下不同集合的各种方法和说明,做个文档,方便自己查找
}
//删除完再加入进来
//或者
//队列如果空,就直接加入进来
deque.add(val);
}
//队列栈顶元素为最大值
int peek(){
return deque.peek();
}
}
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//没仔细做,下次补
//出现频率前k高的元素
//我直接用哈希法
//直接对Hashmap的value排序,输出key就可以了
//定义一个存放结果的数组
int[] arr=new int[k];
//将对应值的下标频率进行增加
//key为元素值,value为对应出现的次数
HashMap<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
}
List<Map.Entry<Integer,Integer>> list = new ArrayList<>(map.entrySet());
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
return (o2.getValue()) - o1.getValue();
}
});
int[] ans = new int[k];
for (int i = 0; i < k; i++) {
Map.Entry<Integer, Integer> entry = list.get(i);
ans[i] = entry.getKey();
}
return ans;
//用堆算法待补
}
}