arrays - 将全为零的给定数组转换为目标数组

Question

最近遇到一道面试题。我尝试解决它，但面试官正在寻找更好的解决方案。问题是:

Given a source array containing zeroes and target array containing numbers, return the smallest number of steps in which you can obtain target from source. You are only allowed to do following operation: You can increase the values of source array elements each by 1 from index L to index R in one operation.

我的想法:

Let array be [4,2,3,5] 
cnt=0;
For each sub-array with only non-zero element, subtract minimum of that sub-array from each of the element of that sub-array. Count increases by sum of mins in each subarray
So array becomes :
After first step : [2,0,1,3] cnt+=1*2 (because only one subarray)
After second step : [0,0,0,2] cnt+=2+1 (because two subarray, each requiring an increment operation)
After second step : [0,0,0,0] cnt+=2

有人可以帮助找到更好的算法吗？我也在想是否也可以使用线段树/二叉索引树但无法提出解决方案。

Answer 1

有一个简单的 O(n) 运行时、O(1) 内存解决方案。

将 target 数组视为具有给定高度的山脉。最小操作数是为构建该山脉而必须放下的非断开连接的 1 层高度层数。

但更简单的思考方式是，如果您从任一方向穿越该山脉，您必须爬上的总距离。

这是一个 C++ 实现。

int minNumberOperations(const vector<int>& target) {
  int result = 0, prev = 0;
  for (int height : target) {
    result += max(0, height - prev);
    prev = height;
  }
  return result;
}