题解 | #发奖金# 两次遍历

力扣原题135.分发糖果：https://leetcode.cn/problems/candy/

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    int N;
    while (cin >> N) {
        vector<int> grade(N);
        for (int i = 0; i < N; i++) {
            cin >> grade[i];
        }
        vector<int> dp(N, 1);
        // 从左往右遍历，右边比左边成绩高则多加1w
        for (int i = 1; i < N; i++) {
            if (grade[i] > grade[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
        }
        // 从右往左遍历，左边比右边成绩高 而且 左边的奖金小于右边时，给左边加奖金
        for (int i = N - 2; i >= 0; i--) {
            if (grade[i] > grade[i + 1] && dp[i] <= dp[i + 1]) {
                dp[i] = dp[i + 1] + 1;
            }
        }
        cout << accumulate(dp.begin(), dp.end(), 0) << endl;
    }
    return 0;
}

时间复杂度：O(n)，用于遍历grade数组

空间复杂度：O(n)，用于存储dp数组