代碼隨想錄算法訓(xùn)練營(yíng)day13 | 題目239、題目347、題目155
題目一描述
給你一個(gè)整數(shù)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字。滑動(dòng)窗口每次只向右移動(dòng)一位。
返回 滑動(dòng)窗口中的最大值 。
示例 1：
輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3
輸出：[3,3,5,5,6,7]
解釋?zhuān)?br>
滑動(dòng)窗口的位置 | 最大值
[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
解題思路
設(shè)置一個(gè)雙端隊(duì)列，使用單調(diào)隊(duì)列，頭部是最大值，尾部比較小。
每次滑動(dòng)窗口獲得新的數(shù)據(jù)，將其從尾部往前比較，比它小的都移除，直到遇到大于等于這個(gè)數(shù)的元素停下。
滑動(dòng)窗口移動(dòng)移除最左邊元素的時(shí)候，若是與隊(duì)列內(nèi)最大值相等，則同步移除隊(duì)列內(nèi)元素。
每次移動(dòng)的滑動(dòng)窗口內(nèi)最大值都是隊(duì)列頭元素。
代碼實(shí)現(xiàn)
方法一：
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;
}
}
題目二描述
給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k ，請(qǐng)你返回其中出現(xiàn)頻率前 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, 數(shù)組中不相同的元素的個(gè)數(shù)]
題目數(shù)據(jù)保證答案唯一，換句話(huà)說(shuō)，數(shù)組中前 k 個(gè)高頻元素的集合是唯一的
進(jìn)階：你所設(shè)計(jì)算法的時(shí)間復(fù)雜度 必須 優(yōu)于 O(n log n) ，其中 n 是數(shù)組大小。
解題思路
先放入map統(tǒng)計(jì)詞頻，再根據(jù)詞頻排序，返回頻率最高的前k個(gè)元素。
使用優(yōu)先級(jí)隊(duì)列的小頂堆，維護(hù)一個(gè)大小為k的堆，最后得到的結(jié)果就是最大的前k個(gè)元素。
也可以用選擇排序的方法，把有這些頻率的詞放入下標(biāo)為頻率的數(shù)組，空間換時(shí)間，由于數(shù)組下標(biāo)有從小到大的隱形排序，直接倒序獲得即可。
代碼實(shí)現(xiàn)
方法一：
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;
}
}
技巧總結(jié)
O(n)是小于O(nlogn)的。
找前k個(gè)最大元素，最好用小頂堆，因?yàn)樾№敹衙看纬鲫?duì)列的都是最小的那個(gè)元素，維護(hù)k的隊(duì)列長(zhǎng)度，最后留下的就是前k個(gè)最大元素。
找前k個(gè)最小元素，最好用大頂堆，同理。
學(xué)會(huì)優(yōu)先級(jí)隊(duì)列的初始化，優(yōu)先級(jí)隊(duì)列默認(rèn)是小頂堆
注意最好用compareTo來(lái)比較
學(xué)會(huì)map的遍歷方法，子元素?cái)?shù)據(jù)類(lèi)型是Map.Entry<?,?>
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {}
與堆頂元素比較并有選擇的操作，更有效率。
ArrayList<Integer>[] frequency = new ArrayList[nums.length + 1]; 不會(huì)初始化ArrayList，必須顯式創(chuàng)建。
題目三描述
設(shè)計(jì)一個(gè)支持 push ，pop ，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。
實(shí)現(xiàn) MinStack 類(lèi):
MinStack() 初始化堆棧對(duì)象。
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]
解釋?zhuān)?br>
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 操作總是在 非空棧 上調(diào)用
push, pop, top, and getMin最多被調(diào)用 3 * 104 次
解題思路
維護(hù)一個(gè)輔助棧，同步記錄入棧時(shí)候的目前棧內(nèi)最小值，這樣就永遠(yuǎn)能得到原來(lái)?xiàng)?nèi)的最值了。
代碼實(shí)現(xiàn)
方法一：
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();
*/
技巧總結(jié)
注意如果有比較兩個(gè)Integer相等的情況，要用equals
