知识点
模拟,贪心
思路
我们可以观察到,对于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;
}
};