力扣labuladong一刷day51天单调栈应用
2024-01-03 12:39:35
力扣labuladong一刷day51天单调栈应用
一、239. 滑动窗口最大值
题目链接:https://leetcode.cn/problems/sliding-window-maximum/
思路:滑动窗口最大值,既要维护加入的时间顺序,又要
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
Queue queue = new Queue();
for (int i = 0; i < k; i++) {
queue.push(nums[i]);
}
int j = 0;
res[j++] = queue.getMax();
for (int i = k; i < nums.length; i++) {
queue.pop(nums[i-k]);
queue.push(nums[i]);
res[j++] = queue.getMax();
}
return res;
}
class Queue {
LinkedList<Integer> stack = new LinkedList<>();
void push(int n) {
while (!stack.isEmpty() && n > stack.getLast()) {
stack.pollLast();
}
stack.addLast(n);
}
void pop(int n) {
if (n == stack.getFirst()) {
stack.pollFirst();
}
}
int getMax() {
return stack.getFirst();
}
}
}
文章来源:https://blog.csdn.net/qq_43511039/article/details/135359183
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!