滑動(dòng)窗口的最大值
給定一個(gè)數(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)窗口中的最大值建芙。
示例:
輸入: nums =
[1,3,-1,-3,5,3,6,7], 和 k = 3
輸出:[3,3,5,5,6,7]
解釋:
滑動(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
方法一：暴力
每次都在滑動(dòng)窗口中計(jì)算最大值
public int[] maxSlidingWindow(int[] nums, int k) {
int[] ans=new int[nums.length-k+1];
for (int i = 0; i <= nums.length-k; i++) {
int max=Integer.MIN_VALUE;
for (int j = i; j < i+k; j++) {
if(nums[j]>max){
max=nums[j];
}
}
ans[i]=max;
}
return ans;
}
時(shí)間復(fù)雜度O(nk)，空間復(fù)雜度O(n-k+1)
方法二：利用堆
將在滑動(dòng)窗口中的元素放入堆中砚作，堆頂為最大值
public int[] maxSlidingWindow(int[] nums, int k) {
if(k==0){
return new int[0];
}
int[] ans=new int[nums.length-k+1];
PriorityQueue<Integer> queue=new PriorityQueue<>((o1,o2)->o2-o1);
for(int i=0;i<k-1;i++){
queue.offer(nums[i]);
}
for(int i=0;i<nums.length-k+1;i++){
queue.offer(nums[i+k-1]);
ans[i]=queue.peek();
queue.remove(nums[i]);//移除滑動(dòng)窗口之外的元素
}
return ans;
}
時(shí)間復(fù)雜度O(nlogk)
方法三：雙向隊(duì)列
隊(duì)列中的元素都在滑動(dòng)窗口中窘奏，遞減（可以重復(fù)）
在遍歷過程中：
- 將不在窗口的元素從隊(duì)列中移除
- 將隊(duì)列中比當(dāng)前元素小的移除
- 將當(dāng)前元素添加到隊(duì)列中
- 隊(duì)首元素就是當(dāng)前的最大值
public int[] maxSlidingWindow(int[] nums, int k) {
int[] ans = new int[nums.length - k + 1];
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < k; i++) {
clean(deque, nums[i], nums, i, k);
}
ans[0] = deque.getFirst();
for (int i = k; i < nums.length; i++) {
clean(deque, nums[i], nums, i, k);
ans[i - k + 1] = deque.getFirst();
}
return ans;
}
public void clean(Deque<Integer> deque, int num, int[] nums, int cur, int k) {
if (cur - k >= 0 && deque.getFirst() == nums[cur - k]) {//移除滑動(dòng)窗口之外的元素
deque.pollFirst();
}
while (!deque.isEmpty() && num>deque.getLast() ) {//移除比當(dāng)前更小的元素
deque.pollLast();
}
deque.addLast(num);
}
時(shí)間復(fù)雜度O(n)
新版本：
隊(duì)首：小元素 隊(duì)尾：大元素
public int[] maxSlidingWindow(int[] nums, int k) {
if (k == 0) {
return new int[0];
}
int[] ans = new int[nums.length - k + 1];
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < k - 1; i++) {
removeSmaller(deque, nums[i]);
deque.addFirst(nums[i]);
}
for (int i = 0; i < ans.length; i++) {
int index = i + k - 1;
removeSmaller(deque, nums[index]);
deque.addFirst(nums[index]);
removeOutQueue(deque, nums, k, index);
ans[i] = deque.peekLast();
}
return ans;
}
public void removeSmaller(Deque<Integer> deque, int num) {
while (!deque.isEmpty() && deque.getFirst() < num) {
deque.pollFirst();
}
}
public void removeOutQueue(Deque<Integer> deque, int[] nums, int k, int cur) {
if (cur - k >= 0 && nums[cur - k] == deque.getLast()) {
deque.pollLast();
}
}
隊(duì)列的最大值
請(qǐng)定義一個(gè)隊(duì)列并實(shí)現(xiàn)函數(shù) max_value 得到隊(duì)列里的最大值，要求函數(shù)max_value葫录、push_back 和 pop_front 的均攤時(shí)間復(fù)雜度都是O(1)着裹。
若隊(duì)列為空，pop_front 和 max_value 需要返回 -1
示例 1：
輸入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
輸出:[null,null,null,2,1,2]
示例 2：
輸入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
輸出:[null,-1,-1]
限制
1 <= push_back,pop_front,max_value的總操作數(shù) <= 100001 <= value <= 10^5
使用輔助雙端隊(duì)列米同，隊(duì)首存當(dāng)前的最大值骇扇，整個(gè)隊(duì)列遞減
- push(v)：從隊(duì)尾移除所有小于當(dāng)前的元素x（在移除v之前，必須移除了x面粮，而在移除v之前少孝，最大值不可能是x），再將當(dāng)前元素添加到隊(duì)尾
- pop()：如果隊(duì)首元素等于移除的元素熬苍，則移除隊(duì)首元素
class MaxQueue {
private Queue<Integer> queue = new LinkedList<>();
private Deque<Integer> maxQueue = new LinkedList<>();
public int max_value() {
if (maxQueue.isEmpty()) {
return -1;
}
return maxQueue.getFirst();
}
public void push_back(int value) {
queue.offer(value);
while (!maxQueue.isEmpty() && value > maxQueue.getLast()) {
maxQueue.pollLast();
}
maxQueue.offerLast(value);
}
public int pop_front() {
if (queue.isEmpty()) {
return -1;
}
int value = queue.poll();
if (maxQueue.getFirst() == value) {
maxQueue.pollFirst();
}
return value;
}
}
