Monotonic deque

Questions 1 to 5 of 6

1. 1. What does this program print? ``cpp #include <cstddef> #include <deque> #include <iostream> #include <vector> std::vector<int> window_max(const std::vector<int>& nums, std::size_t k) { std::vector<int> result; if (k == 0) { return result; } std::deque<std::size_t> dq; for (std::size_t i = 0; i < nums.size(); ++i) { if (!dq.empty() && dq.front() + k <= i) { dq.pop_front(); } while (!dq.empty() && nums[dq.back()] <= nums[i]) { dq.pop_back(); } dq.push_back(i); if (i + 1 >= k) { result.push_back(nums[dq.front()]); } } return result; } int main() { std::vector<int> nums{1, 4, 2, 6, 3}; for (int m : window_max(nums, 3)) { std::cout << m << ' '; } std::cout << '\n'; } ``

   4 6 6 36 6 64 6 61 4 2
2. 2. The program below prints the deque after each of the three steps, as the lesson does. What does it print? ``cpp #include <cstddef> #include <deque> #include <iostream> #include <vector> int main() { std::vector<int> nums{2, 2, 1}; std::size_t k = 2; std::deque<std::size_t> dq; for (std::size_t i = 0; i < nums.size(); ++i) { if (!dq.empty() && dq.front() + k <= i) { dq.pop_front(); } while (!dq.empty() && nums[dq.back()] <= nums[i]) { dq.pop_back(); } dq.push_back(i); std::cout << "i=" << i << " adds " << nums[i] << " | deque:"; for (std::size_t idx : dq) { std::cout << ' ' << idx << '(' << nums[idx] << ')'; } std::cout << '\n'; } } ``

   i=0 adds 2 | deque: 0(2) i=1 adds 2 | deque: 0(2) 1(2) i=2 adds 1 | deque: 0(2) 1(2) 2(1)i=0 adds 2 | deque: 0(2) i=1 adds 2 | deque: 1(2) i=2 adds 1 | deque: 2(1)i=0 adds 2 | deque: 0(2) i=1 adds 2 | deque: 1(2) i=2 adds 1 | deque: 2(1) 1(2)i=0 adds 2 | deque: 0(2) i=1 adds 2 | deque: 1(2) i=2 adds 1 | deque: 1(2) 2(1)
3. 3. The code below leaves out the step that removes the front index when it has left the window. What does it print for the list 8 3 2 with k equal to 2? ``cpp #include <cstddef> #include <deque> #include <iostream> #include <vector> int main() { std::vector<int> nums{8, 3, 2}; std::size_t k = 2; std::deque<std::size_t> dq; for (std::size_t i = 0; i < nums.size(); ++i) { while (!dq.empty() && nums[dq.back()] <= nums[i]) { dq.pop_back(); } dq.push_back(i); if (i + 1 >= k) { std::cout << nums[dq.front()] << ' '; } } std::cout << '\n'; } ``

   8 38 83 28 2
4. 4. Put the steps that the lesson runs for each new value in the correct order.

   Use the arrows to put the steps in order.

   1. 1.Remove back indices whose values are less than or equal to the new value↑↓
   2. 2.Add the new index at the back↑↓
   3. 3.Read the front value as the answer once the first full window exists↑↓
   4. 4.Remove the front index if it has slid out of the window↑↓
5. 5. The lesson checks the front with dq.front() + k <= i and not with i - k >= dq.front(). Why?

   + is faster than - on every processorThe deque cannot store an index bigger than kWith size_t, i - k can go below zero and wrap to a huge number, so the check would be wrong in the first stepsfront() returns a signed value that cannot be subtracted from