Codility StoneWall

We are given a sequence of integers representing the height of a wall that we have to build. We should return the minimum number of rectangular blocks needed to build it.

A good hint is that this problem has been included in the Stacks and Queues codility section. If you want more clues, you could have a look at the codility blog, where this problem is discussed and a solution is given.

Actually, I found the discussion in there more confusing than helping. Still I got a couple of elements to think on. I pondered on them, and in the end I came out with a sort of pseudo-code.

I use a stack to keep track of the current status of the wall, each element in it represent a block I am using to reach the current level.
Let's say that I am at the i-th step. The stack reflects the status of the previous step.
Maybe I don't have to do anything. The current level is the same. OK, just move to the next step.
Maybe I have to increase the wall height. That's easy, just put a new block of the right size on top the stack.
Maybe I have to decrease the wall height. That's a bit more complicate. I should remove enough blocks to get the right size, or something less than it. And then add a new block, if required.
And, well, that's it.

Then I wrote a few test cases, C++ for GoogleTest:

TEST(StoneWall, Given) // 1
{
    std::vector<int> input { 8, 8, 5, 7, 9, 8, 7, 4, 8 };
    ASSERT_EQ(7, solution(input));
}

TEST(StoneWall, Simple) // 2
{
    std::vector<int> input { 1, 2, 1 };
    ASSERT_EQ(2, solution(input));
}

TEST(StoneWall, Bad) // 3
{
    std::vector<int> input { 0 };
    ASSERT_EQ(-1, solution(input));
}

1. Provided by codility.
2. A sort of minimal pyramid.
3. As usual, Codility does not care about bad input data. I decided to add a basic check to avoid non-positive input. A more robust solution would have been using assertions (if the data check would be a Somebody Else's Problem) or exceptions. Here I decided to keep it simpler and just return a minus one.

And here is my solution:

int solution(std::vector<int>& input)
{
    if(std::find_if_not(input.begin(), input.end(), [](int cur){ return cur > 0; }) != input.end()) // 1
        return -1;

    int blocks = 0;
    std::stack<int> buffer;

    std::for_each(input.begin(), input.end(), [&](int cur) // 2
    {
        while(!buffer.empty() && cur < buffer.top()) // 3
        {
            buffer.pop();
        }

        if(buffer.empty() || cur > buffer.top()) // 4
        {
            buffer.push(cur);
            ++blocks;
        }
    });

    return blocks;
}

1. The STL find_if_not() is used to ensure all the element in input are positive. Paranoid check not required by codility.
2. Loop on all the elements. Notice that the lambda captures by reference the external variables so that it can modify them in its body.
3. If the previous wall height is taller than the current request, remove block(s) from the stack.
4. Add a new block to the stack to match the current request. Besides, increase the block counter.