[907] Sum of Subarray Minimums

算一個array裡面的 "連續subarray" 的最小值相加

就是 (1,2,3,4) 的話, subarray 是1,2,3,4 跟 (1,2) (2,3) (3,4) (1,2,3) (2,3,4) (1,2,3,4) 

(1,3)跟(2,4)這種因為不連續所以不在這裡定義的subarray. 

一開始想說要開一個int subarray 把它們都存起來

所以想算subarray總共有幾組，也就是 n! 長度的階乘，

但後來發現其實沿路算下去就好了，不需要先把subarray都先存起來

再來就發現超時了 XD

但看起來是對的(吧) 那只好先這樣，晚點我再看看其他人都怎麼寫 XD

int sumSubarrayMins(int* arr, int arrSize){

// printf("arrSize %d\n", arrSize);

long ret=0;

for (int l=1;l<=arrSize;l++)

{

for (int i=0;i<=(arrSize-l);i++)

{

int min=INT_MAX;

for (int j=0;j<l;j++)

{

if (arr[i+j] < min)

min=arr[i+j];

}

ret += min;

}

}

int retInt= ret%(1000000000+7);

return retInt;

}

啊DP好難

20240613 update  原來後來我沒有去看別人怎麼寫嗎XD

說是有一種叫做monotonic stack 的東西，會存遞增或遞減的 item

這裡有一點玄兒～就是你pop出來的東西，去乘上它和前後index的差值，就會是這個 num的貢獻總數。（去看別人的說明就懂了 XD）

最後是會overflow的地方，原來是在相乘完的前面要加上long ! 因為它們幾隻都是int ，自己相乘之後爆掉了。 以上

int sumSubarrayMins(int* arr, int arrSize){

long long ret=0;

int *stack = calloc (arrSize, sizeof(int));

int idx = -1;

int cur,pre,next;

for (int i=0; i<arrSize;i++)

{

if (idx<0 || arr[i]>arr[stack[idx]])

{

stack[++idx]= i ;

continue;

}

while (idx >=0 && arr[i] < arr[stack[idx]])

{

cur = stack[idx];

idx--;

pre = (idx <0)?(-1): stack[idx];

next = i;

ret += arr[cur]* (cur-pre)*(next-cur);

}

stack[++idx]= i ;

}

//pop rest of stack

while (idx >=0)

{

cur = stack[idx];

idx--;

pre = (idx <0)?(-1): stack[idx];

next = arrSize;

ret += ((long) arr[cur]* (cur-pre)*(next-cur)) ;

}

int retInt= ret%(1000000000+7);

return retInt;

}