日期 2024/11/10
LeetCode 出題模式有些改變,原本題目通常是 EMMH,現在會變成 E(M)MHH。
bool hasIncreasingSubarrays(vector<int>& nums, int k) {
const int n = nums.size();
for(int i = 0; i < n; i++) {
int count = 0;
int cur = -1001;
int j = i;
while(j < n && cur < nums[j] && count < k) {
count++;
cur = nums[j];
j++;
}
int count2 = 0;
cur = -1001;
j = i + k;
while(j < n && cur < nums[j] && count2 < k) {
count2++;
cur = nums[j];
j++;
}
if(count == k && count2 == k)
return true;
}
return false;
}
int maxIncreasingSubarrays(vector<int>& nums) {
const int n = nums.size();
// number of strictly increasing
vector<int> prefix(n, 1);
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1])
prefix[i] = prefix[i - 1] + 1;
}
int left = 0;
int right = n / 2;
int ret = 1;
while (left <= right) {
int mid = (left + right) / 2;
if (solve(prefix, mid)) {
ret = max(ret, mid);
left = mid + 1;
} else {
right = mid - 1;
}
}
return ret;
}
bool solve(vector<int>& prefix, int k) {
const int n = prefix.size();
if (k == 0)
return true;
for (int i = 0; i < n; i++) {
int count = 0;
int count2 = 0;
int j = i + k + k - 1;
if (i + k - 1 < n)
count = prefix[i + k - 1];
if (j < n)
count2 = prefix[j];
if (count >= k && count2 >= k)
return true;
}
return false;
}
題目與第一題的差異是自己要找一個 k
數值。
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up