class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] result = new int[nums.length - k + 1];
int curMax = nums[0];
int maxLoc = 0;
int secMax = nums[0];
int secLoc = 0;
Queue<Integer> q = new LinkedList<Integer>();
Map<Integer, Integer> m = new HashMap<Integer, Integer>();
if (k >= nums.length) {
Arrays.sort(nums);
return nums[nums.length - 1];
}
for (int i = 1; i < k; i++) {
if (nums[i] >= curMax) {
curMax = nums[i];
maxLoc = i;
} else if (nums[i] >= secMax) {
secMax = nums[i];
secLoc = i;
}
q.add(nums[i]);
}
for (int j = k; j < nums.length; j++) {
q.remove();
}
}
}
원래 하던것....2가지 포지션을 정해놓고 1빠 2빠를 정해놓고 2빠는 무조건 1빠 뒤에.. 1빠가 지나면 2빠가 1빠가 되는 형식
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n * k == 0) return new int[0];
int [] output = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++) {
int max = Integer.MIN_VALUE;
for(int j = i; j < i + k; j++)
max = Math.max(max, nums[j]);
output[i] = max;
}
return output;
}
}
가장 기본적인 방식... 귀찮아서 이거로 했는데 타임리밋 ㅠ
이걸 쓰다가 뭔가를 생각해낸 좌씨
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] check = new int[nums.length];
Arrays.fill(check, Integer.MIN_VALUE);
int changed = 0;
Map<Integer, Integer> vals = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
vals.put(nums[i], i);
}
Arrays.sort(nums);
int j = 0;
int[] result = new int[nums.length - k + 1];
while (changed < nums.length) {
int m = nums[j];
int loc = vals.get(m);
for (int l = (loc - k >= 0 ? loc - k : 0); l < (loc + k < nums.length ? loc + k : nums.length - 1); l++) {
if (check[l] < m) {
check[l] = m;
j++;
}
}
}
for (int a = 0; a < nums.length - k + 1; a++) {
result[a] = check[a];
}
return result;
}
}
ㅎㅏ
class Solution {
ArrayDeque<Integer> deq = new ArrayDeque<Integer>();
int [] nums;
public void clean_deque(int i, int k) {
// remove indexes of elements not from sliding window
if (!deq.isEmpty() && deq.getFirst() == i - k)
deq.removeFirst();
// remove from deq indexes of all elements
// which are smaller than current element nums[i]
while (!deq.isEmpty() && nums[i] > nums[deq.getLast()]) deq.removeLast();
}
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n * k == 0) return new int[0];
if (k == 1) return nums;
// init deque and output
this.nums = nums;
int max_idx = 0;
for (int i = 0; i < k; i++) {
clean_deque(i, k);
deq.addLast(i);
// compute max in nums[:k]
if (nums[i] > nums[max_idx]) max_idx = i;
}
int [] output = new int[n - k + 1];
output[0] = nums[max_idx];
// build output
for (int i = k; i < n; i++) {
clean_deque(i, k);
deq.addLast(i);
output[i - k + 1] = nums[deq.getFirst()];
}
return output;
}
}
Runtime: 28 ms, faster than 70.80% of Java online submissions for Sliding Window Maximum.
Memory Usage: 54.1 MB, less than 49.37% of Java online submissions for Sliding Window Maximum.
루션이^^