[LeetCode] Find the Power of K-Size Subarrays I

3254. Find the Power of K-Size Subarrays I

You are given an array of integers nums of length n and a positive integer k.

The power of an array is defined as:

  • Its maximum element if all of its elements are consecutive and sorted in ascending order.
  • -1 otherwise.

You need to find the power of all subarrays of nums of size k.

Return an integer array results of size n - k + 1, where results[i] is the power of nums[i..(i + k - 1)].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<int> resultsArray(vector<int>& nums, int k) {
deque<pair<int,int>> dq;
vector<int> res;
for(int i = 0; i < nums.size(); i++) {
while(dq.size() and dq.back().second != nums[i] - 1) dq.pop_back();
dq.push_back({i,nums[i]});
while(dq.size() and dq.front().first <= i - k) dq.pop_front();
if(i >= k - 1) {
if(dq.size() == k) res.push_back(nums[i]);
else res.push_back(-1);
}
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2024/08/18/PS/LeetCode/find-the-power-of-k-size-subarrays-i/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.