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

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

不是递增零数组并将其转换为给定数组，而是以其他方式攻击 - 尝试通过递减使给定数组成为零数组。

在给定数组的顶部构建一个线段树。线段树应该能够回答这个查询 - min(left, right ) - 范围 left 和 right 之间的最小项的索引。
从 range(0, n - 1) 开始，其中 n 是数组的大小。在任何时候，对于 query(left, right) 假设最小元素是 x 并且索引是 indx.
技巧来了。这个想法实际上是不递减范围 left 到 right 之间的元素，因为这很困难。递归调用 range(left, indx - 1) 和 range(indx + 1, right)。对于左侧部分和右侧部分，现在您知道了，您已经从每个元素中递减了 dx。所以现在对于任何元素是 X，你必须像 X - dx.

希望你明白了。我将为此提供 C++ 实现。

编辑

请查看代码并使用笔和纸。你会很有希望地明白这个想法。我在棘手的部分添加了评论。

class Solution {
public:
    vector<int> segmentTree;
    vector<int> arr;
    int n;
    void init() {
        segmentTree.clear();
        const int SIZE  = pow(2, ceil(log((double) n) / log(2.0)) + 1) - 1;
        segmentTree.resize(SIZE, 0);
        build(1, 0, n - 1);
    }

    // O(n)
    int build(int node, int left, int right) {
        if(left == right) {
            return segmentTree[node] = left;
        }
        int leftNode = node << 1;
        int rightNode = leftNode | 1;
        int mid = left + (right - left) / 2;
        int leftIdx = build(leftNode, left, mid);
        int rightIdx = build(rightNode, mid + 1, right);
        return segmentTree[node] = (arr[leftIdx] <= arr[rightIdx]) ? leftIdx : rightIdx;
    }

    int query(int node, int left, int right, int x, int y) {
        if(x > right or y < left) return -1;
        if(left >= x and right <= y) return segmentTree[node];
        int leftNode = node << 1;
        int rightNode = leftNode | 1;
        int mid = left + (right - left) / 2;
        int leftIdx = query(leftNode, left, mid, x, y);
        int rightIdx = query(rightNode, mid + 1, right, x, y);
        if(leftIdx == -1) return rightIdx;
        if(rightIdx == -1) return leftIdx;
        return (arr[leftIdx] <= arr[rightIdx]) ? leftIdx : rightIdx;
    }

    int query(int x, int y) {
        return query(1, 0, n - 1, x, y);
    }

    int convertUtil(int left, int right, int dx) {
        if(left > right) return 0;
        int mid = query(left, right);
        int minElement = arr[mid];

        int cnt = 0; // the number of operation

        // dx is the amount that has been already decremented from this range
        // So you have to treat every element X as (X - dx)
        cnt += (minElement - dx);

        cnt += convertUtil(left, mid - 1, minElement) + convertUtil(mid + 1, right, minElement);

        return cnt;
    }

    int convert(vector<int>& arr) {
        this->arr = arr;
        this->n = arr.size();
        init();
        return convertUtil(0, n - 1, 0);
    }
};

// vector<int> arr {4,2,3,5};
// cout << Solution().convert(arr); // OUTPUT: 7

Answer 2

使用堆栈。运行时间是 O(移动 + 长度)。

数值每增加1，就将(position,end_val)入栈。每次该值减1，移除栈顶元素并将其位置与您当前位置左侧的一个配对。

例如，[5, 3, 2, 5]

process 5: an increase. Stack is now (0,1), (0,2), (0,3), (0,4), (0,5)
process 3: a decrease at index 1. Remove the top two elements from the stack and record these moves (0,0) (0,0). The stack is now (0,1), (0,2), (0,3)
process 2: a decrease at index 2. Remove the top element from the stack and record (0,1). The stack is now (0,1), (0,2)
process 5: an increase at index 3. The stack is now (0,1), (0,2), (3,3), (3,4), (3,5)
process 0 (implied): a decrease at index 4. record (3,3), (3,3), (3,3), (0,3), (0,3)

最后一步：(0,0) (0,0), (0,1), (3,3), (3,3), (3,3), (0,3), ( 0,3).

你可以在 space 上通过单独记录多级位置变化（例如（0,5）为第一步）做得更好，但时间效率是相同的，因为每一步只能改变值加 1.

Answer 3

有一个简单的 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;
}

Answer 4

public int minNumberOperations(int[] target) {
    int ans = target[0];
    for(int i=1; i < target.length; i++){
        if(target[i]>target[i-1]){
            ans += target[i]-target[i-1];
        }
    }
    return ans;
 }

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

Convert a given array with all zeros to a target array

arrays

algorithm

segment-tree

编辑