誰看的最多

今天想到了昨天看到一道acm題目，難度入門級別。“誰看的最多”，題目大概是這樣的：一隊列的人3 2 1 6 4 5，數值的大小表示該人的高度。每個人只能看到前面比他高的人，如1可以看見2、3。但是，如果有人B比他高，那么他就不能看到這那個B之前比B低的人了。如5，因為6比他高，他只能看到6，但看不到6之前的人（如果之前有7、8之類比6高的，5也可以看到）。而4比5低也看不到。

題目想了個大概就沒有想了，又是卡在里動態規劃的狀態里。F(i)表示第i個人看到的人數。如果他前一個人比i低，則i看到的最多只有一個了，就是i-1。如果他比前一個高，則看到的就是前i-1個人第一個比他高的人看的人數加一。如果可以快速找前面i-1的第一個比i高，就可以利用動態規劃的方法了。通過一個數組記錄i前面的第一個比i高的位置，這樣就可以快速找出。

狀態轉移方程：F(i)=若i比i-1高，為F(j)+1，j為前面的第一比i高的；否則為1（i>0。i=0，看到就為0個）

挫挫代碼：

int func10(int a[], int n)
{
    int i,j;
    int maxsee;
    int *see,*tall;

    if (n<0)
    {
        return -1;
    }
    see = (int*)malloc(n*sizeof(int));
    tall = (int*)malloc(n*sizeof(int));

    maxsee = see[0] = 0;
    tall[0] = -1; //之前未有比其高的

    for (i=1; i<n; i++)
    {
        if (a[i] > a[i-1])
        {
            for (j=tall[i-1]; j>0; )
            {
                if (a[i]<=a[j])
                {
                    break;
                }
                j=tall[j];
            }
            if (j==-1)
            {
                see[i] = 0;
                tall[i] = -1;
            }
            else
            {
                see[i] = see[j] +1;
                tall[i] = j;
            }
        }
        else  //a[i]<=a[i-1]
        {
            see[i] = see[i-1]+1;
            tall[i] = i-1;
        }

        maxsee = maxsee<see[i] ? see[i]  : maxsee;
    }

    free(see);
    free(tall);

    return maxsee;

}

又一題。

復習還是不給力。。。繼續。。

畢。

?修訂2013-4-18 ：

在不斷的被虐之后，發現其是這個算法的題目是ACM中一個犀利的數據結構：單調棧的應用(參考博客中的另一篇文章：單調棧：柱形統計圖中最大面積（POJ 2559）)?其實此問題的解決就是單調棧的思想，通過記錄的一些信息模擬單調棧。其算法復雜度和單調棧是一致的。