我来翻译一道 Codility 给出的问题:
你需要建造一堵石墙。这堵墙应该是直的,长度为 N 米,厚度应该保持不变;但是,它在不同的地方应该有不同的高度。墙的高度由一个由 N 个正整数组成的数组 H 指定。H[I] 是从其左端到右侧 I+1 米处的墙的高度。特别地,H[0] 是墙的左端的高度,H[N−1] 是墙的右端的高度。
这堵墙应该由长方体石块建造(即,这些块的所有侧面都是矩形)。你的任务是计算建造这堵墙所需的最小石块数。
编写一个函数:
class Solution { public int solution(int[] H); }
根据一个由N个正整数组成的数组H,指定了墙的高度,需要返回建造该墙所需最少砖块的数量。
例如,给定包含N = 9个整数的数组H:
H[0] = 8 H[1] = 8 H[2] = 5
H[3] = 7 H[4] = 9 H[5] = 8
H[6] = 7 H[7] = 4 H[8] = 8
该函数应返回7。下图显示了七个块的一种可能排列方式。
假设:
N是[1..100,000]范围内的整数; 数组H中的每个元素都是[1..1,000,000,000]范围内的整数。 复杂度:
预期最坏时间复杂度为O(N); 预期最坏空间复杂度为O(N)(不包括所需的输入参数存储)。
我为所提供的问题编写了一个解决方案。以下是算法和代码,
算法
i. 将块计数设置为1,并从数组的第二个元素开始迭代
ii. 如果当前深度与上一个相同,则继续
iii. 如果当前深度更高,则将其推入堆栈并增加计数
iv. 如果当前深度更低,则保持弹出直到当前深度>=peek。之后,如果堆栈大小=0或更高,则将块计数增加1
代码如下,
public static int solution(int[] H) {
Stack<Integer> stack = new Stack<>();
stack.push(H[0]);
int count = 1;
int N = H.length;
for (int i = 1; i < N; i++) {
if (H[i] == stack.peek()) {
continue;
} else if (H[i] > stack.peek()) {
stack.push(H[i]);
count++;
} else {
while (!stack.isEmpty() && H[i] < stack.peek()) {
stack.pop();
}
stack.push(H[i]);
count++;
}
}
return count;
}
这个解决方案没有提供正确的答案,即使我花了一些时间进行调试,也无法找到错误。有人能看出来吗?
下面提供了测试数据集,答案是7(但我得到了8)。
int[] H = new int[9];
H[0] = 8;
H[1] = 8;
H[2] = 5;
H[3] = 7;
H[4] = 9;
H[5] = 8;
H[6] = 7;
H[7] = 4;
H[8] = 8;
谢谢您。
if (heights.size() > 0 && heights.top() == H[i]) { heights.push(H[i]); } else { heights.push(H[i]); blocks++; }
- Martin Berger