題目：給出一個(gè)數(shù)組A拳缠，找出一對(duì) (i, j)使得A[i] <= A[j] (i <= j)并且j-i最大 ，若有多個(gè)這樣的位置對(duì)牍白，返回i最小的那一對(duì)脊凰。
最直接的想法就是對(duì)于每一個(gè) i 從數(shù)組最尾端開(kāi)始向前找到第一個(gè)大于等于 A[i] 的位置 j ，時(shí)間復(fù)雜度O(n^2)茂腥。
pair find(constvector &A)
{
intn?=?A.size();
if(n?==?0)
thrownewinvalid_argument("Array's?size?can't?be?0!");
inttarget_i?=?0,?target_j?=?0;
intmax_len?=?0;
for(inti?=?0;?i?<?n;?++i)
{
intj;
for(j?=?n-1;?j?>=?i;?--j)
if(A[j]?>=?A[i])
break;
if(j-i+1?>?max_len)
{
target_i?=?i;
target_j?=?j;
max_len?=?j-i+1;
}
}
returnmake_pair(target_i,?target_j);
}
我們對(duì)上述算法稍作優(yōu)化狸涌。當(dāng)i=0時(shí)，我們假設(shè)找到的大于A[i]的最右位置是j0最岗，那么對(duì)于i=1時(shí)帕胆，我們根本就不需要考慮小于j0的位置，因?yàn)樗鼈兊膮^(qū)間長(zhǎng)度都小于j0+1般渡，不可能成為最優(yōu)解懒豹。
pair find(constvector &A)
{
intn?=?A.size();
if(n?==?0)
thrownewinvalid_argument("Array's?size?can't?be?0!");
inttarget_i?=?0,?target_j?=?0;
intmax_len?=?0;
for(inti?=?0;?i?<?n;?++i)
{
intj;
for(j?=?n-1;?j?>?target_j;?--j)//?此處只需檢查到target_j
if(A[j]?>=?A[i])
break;
if(j-i+1?>?max_len)
{
target_i?=?i;
target_j?=?j;
max_len?=?j-i+1;
}
}
returnmake_pair(target_i,?target_j);
}
但時(shí)間復(fù)雜度仍然是O(n^2)的。我們可以繼續(xù)接著上面的思路優(yōu)化驯用。其實(shí)對(duì)于位置 i 求最后一個(gè)大于等于它的位置脸秽，不需要每次都從數(shù)組尾部向前找，我們可以通過(guò)改進(jìn)這個(gè)地方將時(shí)間復(fù)雜度變?yōu)镺(n)蝴乔。
過(guò)程是這樣的记餐，對(duì)于 i ，我們先找到 i 及其右端的最大元素的位置 j 薇正，檢查是否比當(dāng)前記錄的最優(yōu)解更優(yōu)片酝，更新。然后考慮 j+1及其右端的最大元素位置是否大于等于A[i]挖腰，若是雕沿，令 j 等于該位置，重復(fù)如上過(guò)程猴仑，若否审轮，那么從位置i+1重新開(kāi)始，但j仍然從當(dāng)前位置考慮即可，原因上面已說(shuō)明断国。這樣時(shí)間復(fù)雜度就成O(n)的了贤姆。
具體請(qǐng)參考代碼
pair find(constvector &A)
{
intn?=?A.size();
if(n?==?0)
thrownewinvalid_argument("Array's?size?can't?be?0!");
vector?right_max_pos(n);
right_max_pos[n-1]?=?n-1;
for(inti?=?n-2;?i?>=?0;?--i)
{
if(A[i]?>?A[right_max_pos[i+1]])
right_max_pos[i]?=?i;
else
right_max_pos[i]?=?right_max_pos[i+1];
}
intmax_len?=?0;
inttarget_i,?target_j;
inti?=?0,?j?=?0;
while(j?<?n)
{
j?=?right_max_pos[j];
if(A[j]?>=?A[i])
{
if(j-i+1?>?max_len)
{
target_i?=?i;
target_j?=?j;
max_len?=?j-i+1;
}
++j;
}
else
++i;
}
returnmake_pair(target_i,?target_j);
}
