239. Sliding Window Maximum
Đề Bài
You are given an array of integers 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.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: 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
Example 2:
Input: nums = [1], k = 1 Output: [1]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n×m)
💾 Không gian
O(n×m)
Lời Giải
C++
0239-sliding-window-maximum.cpp
class Solution {
public:
int dp[18][100005];
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
dp[0][i + 1] = nums[i];
}
int m = log2(n) + 1;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n - (1 << i) + 1; ++j) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + (1 << (i - 1))]);
}
}
vector<int> ans;
for (int j = 1; j <= n - k + 1; ++j) {
int l = j;
int r = j + k - 1;
int i = log2(r - l + 1);
ans.push_back(max(dp[i][l], dp[i][r - (1 << i) + 1]));
}
return ans;
}
};
Python
0239-sliding-window-maximum.py
from sortedcontainers import SortedList
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
st = SortedList()
l = 0
n = len(nums)
ans = []
for r in range(n):
st.add(nums[r])
if r - l + 1 == k:
ans.append(st[-1])
st.remove(nums[l])
l += 1
return ans