aboutsummaryrefslogtreecommitdiff
path: root/sliding_window_max.cpp
blob: 8468604a9e7433dfd505b042ecb474b229dabf0a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 239. Sliding Window Maximum
#include "leetcode.h"

/*
 * 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 each window. each time the sliding window moves
 * right by one position. return the max sliding window.
 */

class Solution {
public:
  vector<int> maxSlidingWindow(vector<int> &nums, int k) {
    deque<int> dq;
    vector<int> ans;
    for (int i = 0; i < nums.size(); i++) {
      if (!dq.empty() && dq.front() == i - k)
        dq.pop_front();
      while (!dq.empty() && nums[dq.back()] < nums[i])
        dq.pop_back();
      dq.push_back(i);
      if (i >= k - 1)
        ans.push_back(nums[dq.front()]);
    }
    return ans;
  }
};

int main() {
  Solution obj;
  vector<int> n1 = {1, 3, -1, -3, 5, 3, 6, 7}, n2 = {1};
  for (auto i : obj.maxSlidingWindow(n1, 3))
    printf("%d ", i); // expect: 3,3,5,5,6,7
  printf("\n");
  for (auto i : obj.maxSlidingWindow(n2, 1))
    printf("%d ", i); // expect: 1
  printf("\n");
}