学步园

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

class Solution {
public:
    int candy(vector<int> &ratings) {
        int n=ratings.size();
        vector<int> &t=ratings;
        vector<int> r(n,0);

        int i=0;
        while(true){
            int j=i;
            //down 
            while(j<n-1&&t[j+1]<t[j])  j++;
            int k=i;
            while(true) {
                if(k==i) r[k]=max(j-k+1,r[k]); //@warning the handle of the leftest element
                else r[k]=j-k+1;
                if(k==j) break;///end while
                k++;
            }
            
            //equal
            i=j;
            while(j<n-1&&t[j+1]==t[j]) j++,r[j]=1;
            
            //up
            i=j;
            while(j<n-1&&t[j+1]>t[j]) j++;
            k=i;
            while(true){
                r[k]=k-i+1;
                if(k==j) break;
                k++;
            }
            
            i=j;//@loop i
            if(i>=n-1) break;//end loop when i has reach the right endian of array t
        }
        int res=0;
        for(i=0;i<n;i++) res+=r[i];///@@error: here array r[i] fault as t[i]
        return res;
    }
};

此题关键是i，j，k的线性扫描。

j绑定到水洼的左边界，

k绑定到j右边的第一个不小于A[j]的右边界；如果k溢出（找不到)，则k改绑定到右边最大的值。

然后计算(j,k)水洼的值。

再然后令i=k,开始新循环。

起名字（左边界，右边界）最好对应变量名字对仗，方便理解。

class Solution {
public:
    int trap(int A[], int n) {
        
        int area=0;
        int i=0;
        while(i<n){
            int j=i;
            int mL=A[i];//水洼左边界
            
            while(j<n-1&&A[j]<=A[j+1]) j++,mL=A[j];//A[j] is the extremal value after i ///@@@error:j++,mL=A[j],fault as lst=A[j],j++, then lst logically get a left smaller value
            
            int k=j+1; if(k>=n) break;
            int mR=0;//临时右边界
            while(k<n&&A[k]<mL) {//find a extremal 
                if(A[k]>mR) mR=A[k];
                k++;
            }
            
            int m=(k<n?mL:mR);///@error: m=(k<n?A[k]:mR); should be  m=(k<n?mL:mR);
            if(m==0) break; //没有水洼了
            for(k=j+1;A[k]<m;k++) area+=m-A[k];
            i=k;
        }
        return area;
    }
};

程序2:

class Solution {
public:
    int trap(int A[], int n) {
        if(n==0) return 0;
        int lH=A[0];//水洼左边界
        int area=0;
        int i=0;while(i<n-1){
            int rH=0,rX=i;  //i~rX 为水洼。rH为水洼临时右边界，初始为0
            int j;for(j=i+1;j<n;j++) {
                if(A[j]>=lH) {rX=j,rH=A[j];break;}//>=左边界的水洼右边界j
                if(A[j]>rH) rX=j,rH=A[j];//临时右边界
            }
            if(rX==i) break;//该水洼没有右边界。则后面也不存在水洼。
            //计算水洼面积
            int H=min(lH,rH);
            for(int k=i+1;k<rX;k++){ area+=H-A[k]; }
            //进入下一个水洼
            i=rX;lH=rH;
        }
        return area;
    }
};