题目描述

见旁边那个大佬

样例

算法1

(单调栈) $O(n)$ 只需1000ms

时间复杂度

参考文献

python 代码

class Solution:
    def minNumberOperations(self, nums: List[int]) -> int:
        ans = 0
        stack = [0]
        for num in nums:
            max_ = 0
            while(stack and stack[-1] >= num ):
                max_ = max(max_, abs(stack.pop() - num))
            ans += max_
            stack.append(num)
        while(stack[-1]):
            ans += abs(stack.pop() - stack[-1])
        return ans

算法2 比较连续元素

(贪心) $O(n)$

当当前元素a大于之前元素时，我们至少需要a - pre操作来做比较
累积操作总数，是最小界(LowerBound 不知道中文咋翻译 没学过中文高数.), 所以是最适的

时间复杂度

参考文献

Python 代码 888ms

def minNumberOperations(self, A):
        res = pre = 0
        for a in A:
            res += max(a - pre, 0)
            pre = a
        return res

c++ 版本 280ms

int minNumberOperations(vector<int>& A) {
        int res = 0, pre = 0;
        for (int a: A) {
            res += max(a - pre, 0);
            pre = a;
        }
        return res;
    }

注:给自己的笔记 贪心只选当前看最好的