3738. Longest Non-Decreasing Subarray After Replacing at Most One Element
You are given an integer array nums.
You are allowed to replace at most one element in the array with any other integer value of your choice.
Return the length of the longest non-decreasing subarray that can be obtained after performing at most one replacement.
An array is said to be non-decreasing if each element is greater than or equal to its previous one (if it exists).
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
39
| class Solution {
public:
int longestSubarray(vector<int>& nums) {
int n = nums.size();
if(n <= 2) return n;
vector<pair<int,int>> range{{0,0}};
for(int i = 1; i < n; i++) {
if(nums[i] < nums[i-1]) range.push_back({i,i});
range.back().second = i;
}
int res = 0;
for(int i = 0; i < range.size(); i++) {
res = max(res, range[i].second - range[i].first + 2);
if(i + 1 < range.size()) {
auto [l,r] = range[i+1];
if(l == r) {
res = max(res, range[i].second - range[i].first + 2);
if(i + 2 < range.size()) {
if(nums[range[i].second] <= nums[r+1]) res = max(res, range[i+2].second - range[i].first + 1);
}
} else if(nums[range[i].second] <= nums[l+1]) {
res = max(res, r - range[i].first + 1);
}
}
if(i) {
auto [l,r] = range[i-1];
if(l == r) {
res = max(res, range[i].second - range[i].first + 2);
if(i >= 2) {
if(nums[range[i].first] >= nums[l-1]) res = max(res, range[i].second - range[i-2].first + 1);
}
} else if(nums[range[i].first] >= nums[r-1]) {
res = max(res, range[i].second - l + 1);
}
}
}
return min(res,n);
}
};
|
