题目描述

给你一个整数数组 target 和一个数组 initial，initial 数组与 target 数组有同样的维度，且一开始全部为 0。

请你返回从 initial 得到 target 的最少操作次数，每次操作需遵循以下规则：

• 在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1。

答案保证在 32 位有符号整数以内。

样例

输入：target = [1,2,3,2,1]
输出：3
解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。
[0,0,0,0,0] 将下标为 0 到 4 的元素（包含二者）加 1 。
[1,1,1,1,1] 将下标为 1 到 3 的元素（包含二者）加 1 。
[1,2,2,2,1] 将下表为 2 的元素增加 1 。
[1,2,3,2,1] 得到了目标数组。

输入：target = [3,1,1,2]
输出：4
解释：(initial)[0,0,0,0] -> [1,1,1,1] ->
    [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target) 。

输入：target = [3,1,5,4,2]
输出：7
解释：(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] 
    -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target)。

输入：target = [1,1,1,1]
输出：1

限制

• 1 <= target.length <= 10^5
• 1 <= target[i] <= 10^5

算法1

(贪心，单调栈) $O(n)$

1. 贪心的来看，对于每个山峰，我们需要通过单独累加山峰的位置来削掉山峰。这里我们维护一个单调不减的栈来模拟这个过程。
2. 如果当前元素的高度小于等于栈顶元素（出现了山峰)，则栈顶元素所在的集合就需要提前单独累加，累加之后，就可以视作与当前元素在同一个集合了（之后可以一起累加）。下一个栈顶再来与当前元素比较。
3. 形式上来看，如果 $target(i) \le target(st.top())$，则栈顶出栈，记为 $top$，此时 $top$ 所在的集合需要单独累加的次数就是 $target(top) - \max(target(i), target(st.top())$，注意，如果 $st.top()$ 不存在则直接减去 $target(i)$。
4. 以此类推，满足单点不减的条件后当前元素进栈。

时间复杂度

• 每个位置最多进栈一次，出栈一次，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储栈。

C++ 代码

class Solution {
public:
    int minNumberOperations(vector<int>& target) {
        const int n = target.size();
        int ans = 0;
        stack<int> st;

        for (int i = 0; i < n; i++) {
            while (!st.empty() && target[i] <= target[st.top()]) {
                int top = st.top();
                st.pop();

                if (st.empty())  ans += target[top] - target[i];
                else ans += target[top] - max(target[i], target[st.top()]);
            }

            st.push(i);
        }

        return ans + target[st.top()];
    }
};

算法2

(贪心，线性扫描) $O(n)$

1. 初始时，我们至少需要 $target(0)$ 次累加使第一个位置符合要求，但累加的过程中也可以顺便累加后边的一些位置。
2. 我们考察两个位置之间的差值，如果 $target(i + 1) > target(i)$，则位置 $i + 1$ 至少要付出 $target(i + 1) - target(i)$ 次累加。其余情况，$i + 1$ 位置都可以被 $i$ 位置顺便累加。

时间复杂度

• 每个位置遍历一次，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int minNumberOperations(vector<int>& target) {
        const int n = target.size();
        int ans = target[0];

        for (int i = 0; i < n - 1; i++)
            ans += max(target[i + 1] - target[i], 0);

        return ans;
    }
};

算法3

(贪心，RMQ) $O(n \log n)$

1. 对于一个给定的区间，最优解第一步一定是先整体填充最小值。
2. 对于这道题来说，一开始待求区间为 [0, n - 1]，第一步找到一个最小值的位置 $t$，答案累加 $target(t)$，我们将区间分为两部分，[0, t - 1] 和 [t + 1, n - 1]，然后分别求最小值累加答案。
3. 形式上来讲，对于当前区间 [l, r]，以及当前已经填充的高度 $last$，我们找到当前区间最小值的位置 $t$，答案累加 $target(t) - last$，然后分别递归处理 [l, t - 1] 和 [t + 1, r]，并修改 $last$ 为 $target(t)$。
4. 求区间最小值可以用线段树或者 RMQ 来解.

时间复杂度

• 预处理 RMQ 需要 $O(n \log n)$ 的时间。
• 递归每次都会将区间长度减少 1，每次分割时间复杂度为 $O(1)$（如果用线段树则为 $O(\log n)$）。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n \log n)$ 的额外空间存储 RMQ 的数据结构。

C++ 代码

class Solution {
private:
    vector<vector<int>> m, who;
    vector<int> log;
    int ans;

    int query(int l, int r) {
        int p = log[r - l + 1];
        if (m[p][l] < m[p][r - (1 << p) + 1])
            return who[p][l];

        return who[p][r - (1 << p) + 1];
    }

    void solve(const vector<int> &target, int last, int l, int r) {
        if (l > r) return;

        int t = query(l, r);
        ans += target[t] - last;


        solve(target, target[t], l, t - 1);
        solve(target, target[t], t + 1, r);
    }

public:
    int minNumberOperations(vector<int>& target) {
        const int n = target.size();
        const int M = 17, INF = 1000000000;

        log.resize(n + 1);

        m.resize(M, vector<int>(n, INF));
        who.resize(M, vector<int>(n, INF));

        log[1] = 0;
        for (int i = 2; i <= n; i++)
            log[i] = i >> (log[i - 1] + 1) ? log[i - 1] + 1 : log[i - 1];

        for (int i = 0; i < n; i++) {
            m[0][i] = target[i];
            who[0][i] = i;
        }

        for (int j = 1; j < M; j++)
            for (int i = 0; i + (1 << j) - 1 < n; i++)
                if (m[j - 1][i] < m[j - 1][i + (1 << (j - 1))]) {
                    m[j][i] = m[j - 1][i];
                    who[j][i] = who[j - 1][i];
                } else {
                    m[j][i] = m[j - 1][i + (1 << (j - 1))];
                    who[j][i] = who[j - 1][i + (1 << (j - 1))];
                }

        ans = 0;
        solve(target, 0, 0, n - 1);
        return ans;
    }
};