将具有所有零的给定数组转换为目标数组
最近我遇到了一个面试问题。我试着解决这个问题，但是面试官正在寻找一个更好的解决方案。问题是：
给定包含零的源数组和包含数字的目标数组，则返回可以从源获取目标的最小步骤数。只允许执行以下操作:在一次操作中，可以将源数组元素的值从索引L增加1到索引R。
我的想法：
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有人能帮助找到更好的算法吗？我还在考虑是否也可以使用段树/二叉树索引树，但无法找到解决方案。
回答 4
Stack Overflow用户
发布于 2018-05-21 14:17:49
不要增加零数组并将其转换成给定的数组，相反，攻击是相反的--尝试通过递减使给定数组变为零数组。
- 在给定数组的顶部构建段树。段树应该能够回答这个查询--
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: 7Stack Overflow用户
发布于 2020-07-25 16:17:44
这里有一个简单的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;
}Stack Overflow用户
发布于 2018-05-21 16:33:39
用一堆。运行时间为O(移动+长度)。
每次值增加1时，将(位置、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)。
您可以通过记录多个级别的位置变化来在空间上做得更好(例如，(0,5)对于第一次移动)，但是时间效率是相同的，因为每次移动只能将值更改1。
https://stackoverflow.com/questions/50450519
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号