समस्या
Slide a window of size k across the list one step at a time and report the maximum inside each window. A deque keeps this O(n).
Implement window_maximums(numbers, k).
Input
numbers: The list of integers. k: The window size.
Output
Return the maximum of each window, left to right.
सीमाएँ
1 ≤ k ≤ length ≤ 200,000
उदाहरण
इनपुट:
k = 3
numbers = [1, 3, -1, -3, 5, 3, 6, 7]
अपेक्षित आउटपुट:
expected = [3, 3, 5, 5, 6, 7]इनपुट:
long long k = 3;
std::vector<long long> numbers = {1, 3, -1, -3, 5, 3, 6, 7};
अपेक्षित आउटपुट:
std::vector<long long> expected = {3, 3, 5, 5, 6, 7};इनपुट:
long k = 3;
long[] numbers = new long[] {1, 3, -1, -3, 5, 3, 6, 7};
अपेक्षित आउटपुट:
long[] expected = new long[] {3, 3, 5, 5, 6, 7};व्याख्या
Windows [1,3,-1], [3,-1,-3], [-1,-3,5], … have maxima 3, 3, 5, 5, 6, 7.
इनपुट:
k = 1
numbers = [4, 2]
अपेक्षित आउटपुट:
expected = [4, 2]इनपुट:
long long k = 1;
std::vector<long long> numbers = {4, 2};
अपेक्षित आउटपुट:
std::vector<long long> expected = {4, 2};इनपुट:
long k = 1;
long[] numbers = new long[] {4, 2};
अपेक्षित आउटपुट:
long[] expected = new long[] {4, 2};व्याख्या
Windows of one element are the elements themselves: [4, 2].
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Maximum window से बाहर निकलते ही गायब हो सकता है, इसलिए आपको value और index दोनों के हिसाब से update होने वाली structure चाहिए.
संकेत 2
Candidate indices को values के decreasing order में रखें, और current window के बाहर की किसी भी चीज़ को drop करें.
संकेत 3
First full window और size one वाले windows का ध्यान रखें; हर answer एक fully formed window का होना चाहिए.
अपेक्षित जटिलता
समय O(n), अतिरिक्त स्थान O(k)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।