Leetcode 1526 Minimum Number of Increments on Subarrays to Form a Target Array

题意

给定一个数组比方[1, 2, 3，2，1]，每次变革一个区间，让区间里的值+1， 求从[0, 0,0,0,0]到[1, 2, 3，2，1]须要几步
标题链接

https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/
题解

起首这个数组可以分割成许多过非递增子串，对于每一个非递增子串比如
[3，2，1]须要的步数就是递增子串的开头，那么标题就变成了[3, 2, 1, 2]这种标题（两个非递增子串拼在一起），在1和2之间，我须要增补一个差值，以是标题的答案就是a[0]+累加这个差值，留意第一个非递增子串要列入盘算

1. class Solution {
2. public:
3.     int minNumberOperations(vector<int>& target) {
4.         int res = target[0];
5.         for(int i = 1; i < target.size(); i++) {
6.             if(target[i] > target[i-1]) {
7.                 res += target[i] - target[i-1];
8.             }
9.         }
10.         return res;
11.     }
12. };

复制代码

时间复杂度                              O                      (                      n                      )                          O(n)               O(n)
空间复杂度                              O                      (                      1                      )                          O(1)               O(1)

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金