我正在做这个编程任务。它测试了我们对堆栈及其应用的理解。我发现想出一种可以高效准确地工作的算法非常困难。他们的一些测试用例有 200,000 多棵“树”！虽然我的算法可以适用于少于 10 棵树的更简单的测试用例，但当“树”的数量非常大（从 100 多棵以上）时，它在准确性和效率部门就失败了。
如果你们能给我一个提示或指出正确的方向，我将非常感激。谢谢你。
任务说明
猴子喜欢在树间荡秋千。他们可以直接从一棵树摆动到另一棵树，只要两者之间没有树高于或与两棵树中的任何一棵具有相同的高度。例如，如果有 5 棵高度分别为 19m、17m、20m、20m 和 20m 的树依次排列，那么猴子将能够从一棵树摆动到另一棵树，如下所示：
1. from first tree to second tree 2. from first tree to third tree 3. from second tree to third tree 4. from third tree to fourth tree 5. from fourth tree to fifth tree能够与猴子交流的丛林之王泰山想测试猴子是否知道如何计算可以直接从一棵树摆动到另一棵树的树的总数。但他自己也不是很会数。所以他求助于你，这个国家最好的 Java 程序员，写一个程序来计算丛林不同地区的树木的正确数量。
输入
第一行包含 N，路径中的树数。下一行包含 N 个整数 a1 a2 a3 ... aN，其中 ai 表示路径中第 i 个树的高度，0 < ai ≤ 231 和 2 ≤ N ≤ 500,000。
请注意，为方便起见，上面使用了短符号 N。在你的程序中，你应该给它一个描述性的名字。
输出
在给定的树高列表中，猴子可以直接从一棵树摆动到另一棵树的树对总数。
样本输入 1
4
3 4 1 2
样本输出 1
4
样本输入 2
5
19 17 20 20 20
样本输出 2
5
样本输入 3
4 1
2 21 21 12
样本输出 3
3
这是我的代码。所以这是一个返回猴子可以摆动的树对数的方法。参数是一个输入数组。
我的算法如下：
我们将 numPairs 设置为（数组长度 - 1），因为所有树都可以从一棵摇摆到另一棵。
现在我们找到了额外的 numPairs（额外的树来摆动）。
将第一个输入压入空堆栈
我们进入一个for循环：
直到数组末尾的下一个输入：
情况1：
如果栈顶小于当前输入并且栈的大小等于 1，那么我们用输入替换栈顶。
案例2：
如果栈顶小于当前输入且栈大小大于1，则弹出栈顶，并进入while循环弹出小于当前栈顶的前一个元素。
然后我们在退出 while 循环后推送当前输入。
案例3：
否则，如果不满足上述条件，我们只需将当前输入压入堆栈。
我们退出 for 循环
返回 numPairs
公共 int 解决（int [] arr）{
int input, temp;
numPairs = arr.length-1;
for(int i=0; i<arr.length; i++)
{
input = arr[i];
if(stack.isEmpty())
stack.push(input);
else if(!stack.isEmpty())
{
if(input>stack.peek() && stack.size() == 1)
{
stack.pop();
stack.push(input);
}
else if(input>stack.peek() && stack.size() > 1)
{
temp = stack.pop();
while(!stack.isEmpty() && temp < stack.peek())
{
numPairs++;
temp = stack.pop();
}
stack.push(input);
//numPairs++;
}
else
stack.push(input);
}
}
return numPairs;
}