• 发表于 9个月前
• 阅读 14
• 收藏 0
• 评论 0

# 思路一

``````import java.util.*;

class ListNode {
int val;
ListNode next;

ListNode(int x) {
val = x;
}
}

class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
}
}

public class Solution {
class StackWithMax {
Stack<Integer> m_data = new Stack<>();
Stack<Integer> m_max = new Stack<>();

public void push(int e) {
m_data.push(e);
if (m_max.isEmpty() || m_max.peek() < e) {
m_max.push(e);
} else {
m_max.push(m_max.peek());
}
}

public int peek() {
int result = 0;

if (!m_data.isEmpty()) {
result = m_data.peek();
}

return result;
}

public void pop() {
if (!m_data.isEmpty()) {
m_data.pop();
m_max.pop();
}
}

public int max() {
int result = 0;
if (!m_max.isEmpty()) {
result = m_max.peek();
}
return result;
}

public boolean isEmpty() {
return m_data.isEmpty();
}
}

class QueueWithMax {
StackWithMax input = new StackWithMax();
StackWithMax output = new StackWithMax();

public void push(int e) {
input.push(e);
}

public int peek() {
int result = 0;
if (output.isEmpty()) {
while (!input.isEmpty()) {
output.push(input.peek());
input.pop();
}
}
if (!output.isEmpty()) {
result = output.peek();
}
return result;
}

public void pop() {
if (output.isEmpty()) {
peek();
}
output.pop();
}

public int max() {
return Math.max(input.max(), output.max());
}

public boolean isEmpty() {
return input.isEmpty() && output.isEmpty();
}
}

public ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> list = new ArrayList<>();

if (num != null && num.length >= size && size!=0) {
QueueWithMax queue = new QueueWithMax();
for (int i = 0; i < num.length; i++) {
queue.push(num[i]);
if (i >= size) {
queue.pop();
} else if(i == size-1){
}
}
}

return list;
}

public static void main(String[] args) {
Solution sou = new Solution();
int[] num = { 2, 3, 4, 2, 6, 2, 5, 1 };
for (int n : sou.maxInWindows(num, 0)) {
System.out.print(n + " ");
}
}
}``````

# 思路二

``````import java.util.*;

public class Solution {
public ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> list = new ArrayList<>();

if (num != null && num.length >= size && size > 0) {
for (int i = 0; i < size; i++) {
while (!dq.isEmpty() && num[dq.getLast()] < num[i]) {
dq.removeLast();
}
}
for (int i = size; i < num.length; i++) {
while (!dq.isEmpty() && num[dq.getLast()] < num[i]) {
dq.removeLast();
}
if (dq.getFirst() < i - size + 1) {
dq.removeFirst();
}
}
}

return list;
}
}``````

×