複盤時間
運氣很好的這次殺到第四關了, 不過有些可惜的是好不容易有想法了時間不夠了
在這邊要找出一段subarray, 然後這個subarray的最小值乘上它的長度為一個數
我們要設法找到這個數的最大值, 首先先給出一個O(n³)的解
class Solution {
public:
int maximumScore(vector<int>& nums, int k) {
int res = 0;
for(int i = 0; i <= k; i++){
int min_value = INT_MAX;
for(int j = k; j < nums.size();j++){
for(int q = i; q <= j;q++){
min_value = min(nums[q], min_value);
}
res = max(min_value * (j - i + 1), res);
}
}
return res;
}
};但這上面太慢了, 有沒有辦法可以加快呢, 我想到two pointer, 讓一個pointer從i 指到k , 在上一個pointer從k 指到 尾端, 試圖找出一個最好的解
class Solution {
public:
int maximumScore(vector<int>& nums, int k) {
int res = 0;
int i = 0;
int j = k;
int min_value = INT_MAX;
for(int q = i;q <= j;q++){
min_value = min(nums[q], min_value);
}
res = min_value * (j - i + 1);
while( i <= k){
j++;
if(j >= nums.size()){
i++;
j = k;
min_value = INT_MAX;
for(int q = i; q <= j;q++){
min_value = min(nums[q], min_value);
}
}else{
min_value = min(nums[j], min_value);
res = max(min_value * (j - i + 1), res);
}
}
return res;
}
};小型的側資都可以過,但有一個測資卻會failed
偏偏又大到很難偵錯. 上面這段code到底出錯在哪呢?
class Solution {
public:
int maximumScore(vector<int>& nums, int k) {
int res = 0;
int i = 0;
int j = k;
int min_value = INT_MAX;
for(int q = i; q < j;q++){
min_value = min(nums[q], min_value);
}
while(i <= k){
if(j >= nums.size()){
i++;
j = k;
min_value = INT_MAX;
for(int q = i; q < j;q++){
min_value = min(nums[q], min_value);
}
}else{
min_value = min(nums[j], min_value);
res = max(min_value * (j - i + 1), res);
j++;
}
}
return res;
}
};錯在我j 的移動不是無腦都移, 是只能在當j可以動的時候再移
可是這樣時間複雜度還是在O(n²), 還是太慢了
所以也是無懸念, 估計我只能想到這
那要怎樣才能更快呢
我的two pointer是i 從0 開始走, j從k
但討論區的做法是i 從k 開始往前走, j 從k開始往後走
這樣的好處就是可以避開我們上面為了要找i 到j的最小值, 都還要再花O(n)的時間
而且, 哪邊比較大我們就往那個方向加, 當一邊到盡頭, 就把另一邊繼續走完, 這樣的做法即可一個two pointer就可以搞定, 太神拉 這是鬼吧
class Solution {
public:
int maximumScore(vector<int>& nums, int k) {
int i = k;
int j = k;
int min_value = nums[k];
int res = min_value;
while (i < 0 || j < nums.size()){
int a, b;
a = i <= 0? 0: nums[i-1];
b = j >= nums.size() - 1?0: nums[j + 1];
if(a > b){
i = i - 1;
min_value = min(min_value, a);
}else{
j = j + 1;
min_value = min(min_value , b);
}
res = max(res, (j - i + 1) * min_value );
}
return res;}
};
時間複雜度為O(n)
