题解 | #牛群放牧顺序#

知识点

模拟，贪心

思路

我们可以观察到，对于rating[i]处的数，它的个数只取决于相邻左右两个数中最大的那一个。

为了维护左右的最大值，我们可以使用两个数组l和r分别维护位置i左侧的值和右侧的值。 l[i],r[i]分别代表rating[i]位置为了左边/右边应该取到的次数

l和r与rating等长，都初始化为1（题意的最少喂一次）

首先从左往右遍历rating数组，若rating[i]>rating[i-1]，则l[i]=l[i-1]+1;（至少，多一次即可）。

同理，从右往左遍历rating数组，若rating[i]>rating[i+1]，则r[i]=r[i+1]+1;（至少，多一次即可）

最后，再遍历一次，取ans+=max(l[i],r[i]);

代码c++

#include <cstring>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param ratings int整型vector 
     * @return int整型
     */
    int min_pasture_time(vector<int>& ratings) {
        // write code he                
       int n=ratings.size();
       vector<int>l(n,1);
       vector<int>r(n,1);
       for(int i=1;i<=n-1;i++)
       {
        if(ratings[i]>ratings[i-1])
        {
            l[i]=l[i-1]+1;
        }

       }
       for(int j=n-2;j>=0;j--)
       {
        if(ratings[j]>ratings[j+1])
        {
            r[j]=r[j+1]+1;
        }
       }
       int ans=0;
       for(int i=0;i<n;i++)
       {
        ans+=max(l[i],r[i]);
       }
       return ans;



    }
};