Given an array 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.
- You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
- Could you solve it in linear time?
For example,
- Given nums =
[1,3,-1,-3,5,3,6,7], and k = 3.
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
- Therefore, return the max sliding window as [3,3,5,5,6,7].
C Solution 1:
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
void push(int *heap, int *top, int val) {
heap[(*top)++] = val;
int cur = *top - 1, root = cur / 2;
while (root && heap[cur] > heap[root]) {
int tmp = heap[cur];
heap[cur] = heap[root];
heap[root] = tmp;
cur = root;
root = cur / 2;
}
}
int pop(int *heap, int *top) {
int res = heap[1];
heap[1] = heap[--*top];
int root = 1, left = 2;
while (left < *top) {
if (left + 1 < *top && heap[left + 1] > heap[left]) left++;
if (heap[root] >= heap[left]) return res;
int tmp = heap[root];
heap[root] = heap[left];
heap[left] = tmp;
root = left;
left = 2 * root;
}
return res;
}
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
if (!nums || !numsSize) return 0;
*returnSize = 0;
int *res = malloc((numsSize - k + 1) * sizeof(int));
int *all = malloc((numsSize + 1) * sizeof(int)), topa = 1;
int *done = malloc((numsSize + 1) * sizeof(int)), topd = 1;
int i;
for (i = 0; i < k; i++) push(all, &topa, nums[i]);
res[(*returnSize)++] = all[1];
for (; i < numsSize; i++) {
push(all, &topa, nums[i]);
push(done, &topd, nums[i - k]);
while (topd > 1 && all[1] == done[1]) {
pop(all, &topa);
pop(done, &topd);
}
res[(*returnSize)++] = all[1];
}
return res;
}
C Solution 2:
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
#define MAX(x, y) ((x) > (y) ? (x) : (y))
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
if (!nums || !numsSize) return 0;
int *toleft = malloc(numsSize * sizeof(int));
int *toright = malloc(numsSize * sizeof(int));
toleft[0] = nums[0];
toright[numsSize - 1] = nums[numsSize - 1];
int i;
for (i = 1; i < numsSize; i++) {
toleft[i] = i % k == 0 ? nums[i] : MAX(toleft[i - 1], nums[i]);
int j = numsSize - 1 - i;
toright[j] = j % k == 0 ? nums[j] : MAX(toright[j + 1], nums[j]);
}
*returnSize = 0;
int *res = malloc((numsSize - k + 1) * sizeof(int));
for (i = 0; i < numsSize - k + 1; i++) {
res[(*returnSize)++] = MAX(toright[i], toleft[i + k - 1]);
}
return res;
}
Python Solution 1:
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums: return []
res = []
heap = []
for i in range(k):
heapq.heappush(heap, -nums[i])
res.append(-heap[0])
discards = collections.defaultdict(int)
for i in range(k, len(nums)):
discards[-nums[i - k]] += 1
heapq.heappush(heap, -nums[i])
while discards[heap[0]] > 0:
discards[heap[0]] -= 1
heapq.heappop(heap)
res.append(-heap[0])
return res
Python Solution 2:
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not k or not nums: return []
l = nums[:]
r = nums[::-1]
for i, num in enumerate(l):
if i % k:
l[i] = max(l[i - 1], num)
last = len(nums) % k
for i in range(1, last):
r[i] = max(r[i - 1], r[i])
for i in range(last, len(nums)):
if i % k != last:
r[i] = max(r[i - 1], r[i])
r = r[::-1]
print(l, r)
res = []
for i in range(len(nums) - k + 1):
res.append(max(r[i], l[i + k - 1]))
return res
Python Solution 3:
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums or not k: return []
l = nums[:]
r = nums[:]
for i in range(1, len(nums)):
if i % k:
l[i] = max(l[i - 1], l[i])
j = len(nums) - 1 - i
if j % k:
r[j] = max(r[j + 1], r[j])
return [max(r[i], l[i + k - 1]) for i in range(len(nums) - k + 1)]
Python Solution 4:
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums: return []
heap = [(-num, i) for i, num in enumerate(nums[:k])]
heapq.heapify(heap)
res = []
res.append(-heap[0][0])
for i in range(k, len(nums)):
heapq.heappush(heap, (-nums[i], i))
while heap[0][1] <= i - k:
heapq.heappop(heap)
res.append(-heap[0][0])
return res
Summary:
- The key point is to use heap to track the maximum val.
- But deletion is not O(lg(N)) in heap, so I have to use another heap to check record all the deleted val.
- If the max of both heap is equal, that means this maximum val is not valid. delete and try again.
- The first: 36ms, 80.95%. The second: 32ms, 100%.
- The O(1) solution is smart and can be reused in many sliding-window problem, I think.
LeetCode: 239. Sliding Window Maximum
近期评论