algorithm - 为什么我的算法不适用于 codility 的曼哈顿天际线
问题描述
我正在从 codility 做训练任务。我以 100/100 的速率完成了 StoneWall,但我仍然坚持该任务中曼哈顿天际线问题的主要思想。该任务在此处描述https://app.codility.com/programmers/task/stone_wall/
好吧,当我第一次读到这个问题时,我意识到我应该只计算建造墙的最小石块数量。没有任何关于如何扩展块等的解释。(可能假设包括我必须提前知道它。但我从未处理过这样的问题)。根据我对这个问题的理解,我实现了下一个算法(因为结果是错误的)
public int solution(final int[] H)
{
if (H.length == 1)
{
return 1;
}
int blocks = 0;
int first = 0;
for (int i = 1; i <= H.length; i++)
{
if (i == H.length || H[first] > H[i])
{
for (int k = first; k < i; k++)
{
if (H[k] != 0)
{
for (int t = k + 1; t < i && H[k] <= H[t]; t++)
{
if (H[t] >= H[k])
{
H[t] = H[t] - H[k];
}
else
{
break;
}
}
blocks++;
}
}
first = i;
}
}
return blocks;
}
上面的代码适用于简单的小数组。例如 { 8, 8, 5, 7, 9, 8, 7, 4, 8 }。显然它表现不佳。我想运行它以了解我以正确的方式。但它会返回不正确的结果,例如值在 1...20 范围内的大型数组。问题是我不了解建筑墙过程的主要思想,所以我无法在我的本地复制它。
然后我研究了一下,在 codility 上找到了这个解决方案https://codility.com/media/train/solution-stone-wall.pdf它是说
The intuition is that by extending each stone block to the ground, we obtain a set of
buildings forming the given skyline.
我认为这是一个线索。(我应该将较小的积木堆在较大的积木上。)但后来我看了看可能排列的积木,这让我再次感到困惑。
最后我使用上面的第二张图片实现了它并且效果很好(100% 的代码)
public int solution2(final int[] H)
{
if (H.length == 1)
{
return 1;
}
int blocks = 0;
final ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
stack.push(H[0]);
for (int i = 1; i < H.length; i++)
{
while (stack.size() > 0 && stack.peek() > H[i])
{
stack.pop();
blocks++;
}
if (stack.isEmpty() || stack.peek() < H[i])
{
stack.push(H[i]);
}
}
return blocks + stack.size();
}
有人可以解释一下为什么第一个算法不适用于这项任务吗?