Find Minimums in Sliding Windows
Given a list of N integers and an integer K, find the minimum value in each contiguous sublist (window) of size K. Print these minimums in the order the windows appear. For example, if the list is [1, 3, -1, -3, 5, 3, 6, 7] and K is 3, the windows are [1, 3, -1], [3, -1, -3], [-1, -3, 5], [-3, 5, 3], [5, 3, 6], [3, 6, 7]. The minimums are -1, -3, -3, -3, 3, 3. The output should be -1 -3 -3 -3 3 3.
Input
The first line contains two integers N and K, separated by a space. The second line contains N integers, representing the list of numbers.
Output
Print N - K + 1 integers, the minimums of each sliding window, separated by spaces.
Constraints
1 <= K <= N <= 200000. -10^9 <= A[i] <= 10^9, where A[i] is the i-th element of the list.
Example 1
8 3 1 3 -1 -3 5 3 6 7
-1 -3 -3 -3 3 3
Standard example with K=3. Minimums are -1, -3, -3, -3, 3, 3.
Example 2
5 5 10 4 8 2 1
1
Window size equals array size. Only one window, its minimum is 1.
Hints
Similar problems
- Minimize Maximum Difference of Elements in IntervalsHard
- Sliding Window MinimumMedium
- Maximum Subarray Sum with Fixed LengthMedium
- Largest Element in PrefixMedium
- Longest Prefix With Maximum FrequencyMedium
- Longest Substring With At Most K Distinct CharactersMedium
More topics: Sliding Window problems, Queue and Deque problems, Heap and Priority Queue problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
8 3 1 3 -1 -3 5 3 6 7
5 5 10 4 8 2 1