题解 | #牛群放牧顺序# bfs 求最长上升路径

知识点

bfs

思路

每个点的应该放牧的值实际上是左右两侧最长上升路径的节点个数。可以找出最低的点，做多源bfs从而找到每个点的最长上升路径，这一步可以用bfs或者dijkstra算法。因为每个点在左右两侧的大小关系是固定的，每个点最多入堆常数次，时间复杂度为。

AC Code (C++)

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

        while (q.size()) {
            auto t = q.front();
            q.pop();
            if (t - 1 >= 0 and ratings[t - 1] > ratings[t] and res[t - 1] < res[t] + 1) {
                res[t - 1] = res[t] + 1;
                q.push(t - 1);
            }
            if (t + 1 < n and ratings[t + 1] > ratings[t] and res[t + 1] < res[t] + 1) {
                res[t + 1] = res[t] + 1;
                q.push(t + 1);
            }
        }

        return accumulate(res.begin(), res.end(), 0);
    }
};