C++ code traverse once and has a runtime of 33ms


  • 0
    A

    I know it's not a standard DP algorithm, I named the array as "dp" just because of my habits.

    class Solution {
    public:
        int candy(vector<int>& r) {
            int n=r.size();
            if(n==0)
                return 0;
            vector<int> dp(n,0);
            dp[0]=1;
            for(int i=1;i<n;++i)
            {
                
                if(r[i]>r[i-1])
                {
                    dp[i]=1+dp[i-1];
                }
                else if(r[i]<r[i-1])
                {
                    while(i<n&&r[i]<r[i-1])
                        ++i;
                    dp[i-1]=1;
                    for(int j=i-2;j>=0&&r[j]>r[j+1]&&dp[j]<=dp[j+1];--j)
                        dp[j]=dp[j+1]+1;
                    --i;
                }
                else
                {
                    dp[i]=1;
                }
            }
            int cnt=0;
            for(auto a:dp)
                cnt+=a;
            return cnt;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.