Sliding Window Maximum (H)
題目
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[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
Example 2:
Input: nums = [1], k = 1
Output: [1]
Example 3:
Input: nums = [1,-1], k = 1
Output: [1,-1]
Example 4:
Input: nums = [9,11], k = 2
Output: [11]
Example 5:
Input: nums = [4,-2], k = 2
Output: [4]
Constraints:
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length
題意
給定一個陣列和一個定長視窗，將視窗在陣列上從左到右滑動，記錄每一步在當前視窗中的最大值，
思路
-
優先佇列
維護一個優先佇列，存盤一個數值對(nums[index], index)，遍歷陣列，計算當前視窗的左邊界left，將當前數字加入到優先佇列中，查看當前優先佇列中的最大值的下標是否小于left，如果是則說明該最大值不在當前視窗中，出隊，重復操作直到最大值在當前視窗中，并加入結果集，
-
雙向佇列
維護一個雙向佇列，存盤下標，遍歷陣列，計算當前視窗的左邊界left，如果隊首元素小于left則出隊；接著從隊尾開始，將所有小于當前元素的下標依次出隊，最后將當前下標入隊，這樣能保證每次剩下的隊首元素都是當前視窗中的最大值，
代碼實作
Java
優先佇列
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] ans = new int[nums.length - k + 1];
Queue<int[]> q = new PriorityQueue<>((a, b) -> b[0] - a[0]);
int left = 0;
for (int i = 0; i < nums.length; i++) {
left = i - k + 1;
q.offer(new int[]{nums[i], i});
if (left >= 0) {
while (q.peek()[1] < left) {
q.poll();
}
ans[left] = q.peek()[0];
}
}
return ans;
}
}
雙向佇列
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] ans = new int[nums.length - k + 1];
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
int left = i - k + 1;
if (!q.isEmpty() && q.peekFirst() < left) {
q.pollFirst();
}
while (!q.isEmpty() && nums[i] > nums[q.peekLast()]) {
q.pollLast();
}
q.offerLast(i);
if (left >= 0) {
ans[left] = nums[q.peekFirst()];
}
}
return ans;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/228734.html
標籤：其他
上一篇：并查集-Java實作
下一篇：三角形的最大周長