曼哈顿天际线封面未通过某些测试案例

Question

我正在做关于协调性的练习。我已经花了两天时间解决这个问题，但是我的分数没有提高。我的正确性得分为100％，但由于通过了错误的回答（不是因为时间或空间的复杂性），因此未通过某些性能测试。我的错误结果总是少于预期的答案。有人能想到我需要添加我丢失的石头的情况吗？

这是提示：

您将要建造一堵石墙。墙应笔直且长N米，且厚度应恒定。但是，它在不同的地方应该有不同的高度。墙壁的高度由零索引H的N正整数数组指定。

H[I]是壁的高度，从左端的右边I到I+1几米。特别是，H[0]是墙的左端H[N?1]的高度，是墙的右端的高度。

墙壁应由长方体的石块建造（即，这些块的所有侧面均为矩形）。您的任务是计算建造墙所需的最小块数。

编写一个函数，给定一个零索引H的N正整数数组来指定墙的高度，该函数返回构建墙所需的最小块数。

class Solution { public int solution(int[] H); }

例如，给定的数组H包含N = 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    

该函数应返回7。该图显示了七个块的一种可能排列。

假使，假设：

• N是范围内的整数[1..100,000];
• 数组的每个元素H都是范围内的整数[1..1,000,000,000]。

复杂：

• 预计最坏情况下的时间复杂度为\ $ O（N）\ $;
• 预期的最坏情况下的空间复杂度为\ $ O（N）\ $，超过了输入存储空间（不计算输入参数所需的存储空间）。
• 输入数组的元素可以修改。

这是我的解决方案：

 import java.util.*;

class Solution {
    public int solution(int[] H) {
        // write your code in Java SE 8

        LinkedList<Integer> stack = new LinkedList<Integer>();
        int count = 1;
        int lowest = H[0];
        stack.push(H[0]);

        if(H.length == 1){
            return 1;   
        }
        else{
        for(int i = 1; i<H.length; i++){
            if(H[i] > H[i-1]){
                stack.push(H[i]);
                count++;   
            }
            if(H[i] < lowest){
                while(stack.size() > 0){
                    stack.pop();   
                }
                stack.push(H[i]);
                lowest = H[i];   
                count++;
            }
            if(H[i] < H[i-1] && H[i] > lowest){
                while(stack.size() > 0 && stack.peek() > H[i]){
                    stack.pop();   
                }
                if(stack.size() > 0 && stack.peek() < H[i]){
                    stack.push(H[i]);
                    count++;   
                }
            }
        }
        }

        return count;
    }
}

Answer 1

可以发现的一个可能问题是当H[i]==lowest. 当 时H[i]==lowest，程序应该只用一个最低的块来重置链表。只需将第二个 if 块更正为：

if(H[i] <= lowest){
    while(stack.size() > 0){
        stack.pop();   
    }
    stack.push(H[i]);                
    if (H[i]!=lowest)
    {
        lowest = H[i];
        count++;
    }
}

考虑情况H = {1,4,3,4,1,4,3,4,1}。正确的输出是 7，而您的代码返回 6。

问题出现时i is 6。第三个 if-block 中的 while 循环重置stack为 {3,1}，这导致stack.peek() < H[i]即将到来的 if-block 失败（stack.peek() = H[6] = 3）。

此外，三个 if-block 可以重写为 if-else-if-else-if 块，因为 H[i] 的值只能满足任何 i 的三个条件之一。