用最小长方形覆盖“曼哈顿天际线”

Question

我写这封信是为了解决下面提供的谦卑问题，

你要建一堵石墙。墙应该是直的，长N米，它的厚度应该是恒定的，但是在不同的地方应该有不同的高度。墙的高度由N个正整数的数组H指定。嗨，是墙的高度，从我到I+1米到它的左边的右边。特别是，H是墙的左端高度，HN−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,000,000,000,000,000,000的整数。复杂性：

最坏情况下的时间复杂度为O(N)；最坏情况下的空间复杂度为O(N) (不包括输入参数所需的存储)。

​

​

我为提供的问题编写了一个解决方案。算法和代码如下，

算法

i.设置块计数=1，然后从数组的第二个元素开始迭代 二、如果当前深度与以前相同，请继续进行。 三、如果当前深度较高，则将其推到堆栈中并增加计数。 四.如果当前深度较低，则继续弹出，直到当前深度>=查看为止。之后，如果堆栈大小=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;

谢谢。

Answer 1

我发现了这个bug，虽然它可能是好的分享。原因是新的高度小于peek值，我们将继续弹出实体。因此，如果堆栈不是空的，则新的高度将是相同的或高于堆栈peek值。

如果新的高度相同，这意味着我们已经为高度添加了一个块，而不会添加一个新的块。这种情况需要一个条件，

               if (!stack.isEmpty() && H[i] == stack.peek()) {
                    continue;
                }

下面的代码提供了100% score，

​

​

public 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();
                }

                /*
                 * the new entity is either in same elevation or higher
                 * */

                /*
                * if in same elevation, we already added the block, so keep iterating
                * */
                if (!stack.isEmpty() && H[i] == stack.peek()) {
                    continue;
                }

                stack.push(H[i]);
                count++;
            }
        }

        return count;
    }

Answer 2

Python解决方案

这是我的解决方案包含步骤细节的解决方案

柔弱蟒蛇100%

def solution(H):
"""
Codility 100%
https://app.codility.com/demo/results/trainingQKD6JP-PHA/

Idea is to use stack concept
Compute the minimum number of blocks needed to build the wall.
To build the wall start taking blocks of height one by one.
We need to take care of -
 - the blocked should not be used again
 - this is done only up to blocks height is greater than current
 - why we are using last 8 height block if there is already 8 height block used in previous step?
    reason is 8 is not present in stack top


8,
 8,----- can not use because on stack top 8 is already there
  5,
   7,
    9,
     8,
      7,------ can not use because on stack top 7 is already there
       4,
        8,

This is just example with height, see steps of output for details
 skip8           skip7
            |           |
|           |   |       |
|       |   |   |       |
|       |   |   |       |
|   |   |   |   |       |
|   |   |   |   |   |   |
|   |   |   |   |   |   |
|   |   |   |   |   |   |
|   |   |   |   |   |   |

旧区块-8 5 7 9 8 8

"""

block_count = 0
# stack is used to hold height used to building and remove all the blocks from it,
#  if any of the block of stack is greater than current block(to be added for building)
stack = []
for height in H:
    print(" ")
    print("Current Height " + str(height))
    print("Current stack " + str(stack))
    # Remove all blocks that are bigger than current height, stack should not be empty
    while stack and stack[-1] > height:
        stack.pop()
    print("After remove bigger blocks than current height " + str(stack))

    # stack is not empty and top item of stack is equal to current height
    if stack and stack[-1] == height:
        # Already used this size of block
        print("Already used this size of block " + str(height))
        continue
    else:
        # new block is required, push it's size to the stack
        block_count += 1
        stack.append(height)
        print("Add this block.... " + str(height) + " Minimum Blocks " + str(block_count))

return block_count

Answer 3

另一个在爪哇。更简单，因为我使用了高度> 0的假设。

    public int solution(int[] hs) {
        int squares = 0;
        Stack<Integer> s = new Stack<>();
        s.push(0);

        for (int h: hs) {
            while (s.peek() > h) {
                s.pop();
            }
            if (s.peek() != h) {
                s.push(h);
                ++squares;
            }
        }

        return squares;
    }