题解 | #牛群放牧顺序#
牛群放牧顺序
https://www.nowcoder.com/practice/69f5f2d04d1c41df8d4e0691f6ef6935
考察的知识点:贪心;
解答方法分析:
- 定义了两个等长的数组 left 和 right,用来记录每个元素的左边和右边的最长递增子序列长度。
- 遍历数组 ratings,从前往后,如果当前元素大于前一个元素,则将左边的最长递增子序列长度加 1,否则不变。
- 遍历数组 ratings,从后往前,如果当前元素大于后一个元素,则将右边的最长递增子序列长度加 1,否则不变。
- 定义一个变量 totalPastureTime 来累加左右两边最长递增子序列的较大值。
- 返回 totalPastureTime,即为最小牧场时间。
所用编程语言:C++;
完整编程代码:↓
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param ratings int整型vector * @return int整型 */ int min_pasture_time(vector<int>& ratings) { int n = ratings.size(); vector<int> left(n, 1); vector<int> right(n, 1); for (int i = 1; i < n; i++) { if (ratings[i] > ratings[i - 1]) { left[i] = left[i - 1] + 1; } } for (int i= n - 2; i >= 0; i--) { if (ratings[i] > ratings[i + 1]) { right[i] = right[i + 1] + 1; } } int totalPastureTime = 0; for (int i = 0; i < n; i++) { totalPastureTime += max(left[i], right[i]); } return totalPastureTime; } };