Manhattan cover horizon lacking some test cases

Question

Manhattan cover horizon lacking some test cases

I do coding exercises. I spent two days on this problem without improving my grade. I get 100% of the correctness score, but do not perform some performance tests because it returns the wrong answer (not because of the complexity of time or space). My incorrect results are always less than the expected answer. Can anyone think of a case where I need to add a stone that I am missing?

This is a hint:

You are going to build a stone wall. The wall should be straight and N meters long, and its thickness should be constant; however, it should have different heights in different places. The height of the wall is determined by the zero index by an array of H Npositive integers .
H[I]- wall height from Ito I+1meters to the right of its left end. In particular, H[0]is the height of the left end of the wall, and H[N−1]is the height of the right end of the wall.
The wall should be built of cubic stone blocks (that is, all sides of such blocks are rectangular). Your task is to calculate the minimum number of blocks needed to build the wall.
Write a function that, given an array with a zero index Hof Npositive integers that determines the height of the wall, returns the minimum number of blocks needed to create it.
class Solution { public int solution(int[] H); }
For example, this array Hcontains N = 9integers:
  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    
The function should return 7. The figure shows one possible arrangement of seven blocks.
Let's pretend that:
N- an integer in the range [1..100,000];
Each element of the array His an integer in the range [1..1,000,000,000].
Complexity:
Expected Worst Time Complexity - \ $ O (N) \ $;
The expected worst spatial complexity is \ $ O (N) \ $, outside of the input storage (not counting the storage needed for the input arguments).
Elements of input arrays can be changed.

This is my decision:

 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;
    }
}

+4

java algorithm

user137717 07 . '14 4:12

6

import java.util.*;

class Solution {
    public int solution(int[] H) {
        Stack<Integer> stack = new Stack<Integer>();
        int count = 1;

        stack.push(H[0]);

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

+3

dorado 03 . '14 17:05

Java Solution 100/100, Stack.

https://codility.com/demo/results/demoX7Z9X3-HSB/

:

import java.util.ArrayList;
import java.util.List;

public class StoneWall {

      public int solution(int[] H) {
          int len = H.length;
          Stack<Integer> stack = new Stack<>(len);
          int blockCounter = 0;

          for (int i = 0; i < len; ++i) {
              int element = H[i];
              if (stack.isEmpty()) {
                  stack.push(element);
                  ++blockCounter;
              } else {
                  while (!stack.isEmpty() && stack.peek() > element) {
                      stack.pop();
                  } 
                  if (!stack.isEmpty() && stack.peek() == element) {
                     continue;
                  } else {
                      stack.push(element);
                      ++blockCounter;
                  }
              }
          }

          return blockCounter;
      }

      public static class Stack<T> {
          public List<T> stack;

          public Stack(int capacity) {
              stack = new ArrayList<>(capacity);
          }

          public void push(T item) {
              stack.add(item);
          }

          public T pop() {
              T item = peek();
              stack.remove(stack.size() - 1);
              return item;
          }

          public T peek() {
              int position = stack.size();
              T item = stack.get(position - 1);
              return item;
          }

          public boolean isEmpty() {
              return stack.isEmpty();
          }
      }
  }

.

+2

moxi 14 . '15 6:25

Scala @moxi:

import scala.collection.mutable


object Solution {
    def solution(H: Array[Int]): Int = {

    val stack =  new mutable.Stack[Int]()

    var blockCounter :Int = 0

    for (i <- 0 to (H.length-1)) {

      var element = H(i)

      if (stack.isEmpty) {
        stack.push(element)
        blockCounter = blockCounter+1
      } else {
        while (!stack.isEmpty && stack.top > element) {
          stack.pop()
        }
        if (!stack.isEmpty && stack.top == element) {

        } else {
          stack.push(element)
          blockCounter = blockCounter+1
        }
      }
    }

    return blockCounter

  }
}

https://codility.com/demo/results/trainingM3BDSK-3YV/

+2

grubjesic 18 . '15 16:13

100/100 Java.

public static int solution(int[] H) {
    // write your code in Java SE 8
    Stack<Integer> s = new Stack<Integer>();
    int count = 1;

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

0

Janath 25 . '16 4:27

; , - . IF FOR , H [i] == .

:

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++;   
    }
}

Also (but this is just a minor thing) using a variable to store the lowest value is not required. By peeping and popping up accordingly, you can easily get the lowest value from the stack. In addition, you can make the code more clear and not compare once with the head on the stack, once with the smallest. Hope this makes sense. Here is my solution.

import java.util.Stack;
class Solution {
    public int solution(int[] H) {
        // write your code in Java SE 8
        Stack<Integer> sittingOn = new Stack<Integer>();
        sittingOn.push(H[0]);
        int counter = 1;
        for(int i = 1; i < H.length; i++){ 
            if(sittingOn.peek() < H[i]){
                counter++;
                sittingOn.push(H[i]);
            } 
            else{
                while (!sittingOn.isEmpty() && sittingOn.peek() > H[i]){
                    sittingOn.pop();
                }
                if (sittingOn.isEmpty() || sittingOn.peek() != H[i]){ 
                    sittingOn.push(H[i]);
                    counter++;
                }
            }
        }   
    }        
    return counter;
}

And here is the compact version that I mentioned in my comment:

import java.util.Stack;
class Solution {
    public int solution(int[] H) {
        // write your code in Java SE 8
        Stack<Integer> sittingOn = new Stack<Integer>();
        sittingOn.push(H[0]);
        int counter = 1;
        for(int i = 1; i < H.length; i++){ 
            while (!sittingOn.isEmpty() && sittingOn.peek() > H[i]){
                sittingOn.pop();
            }
            if (sittingOn.isEmpty() || sittingOn.peek() != H[i]){ 
                sittingOn.push(H[i]);
                counter++;
            } 
        }   
    }        
    return counter;
}

0

Angelo oparah Mar 09 '16 at 11:25

source share

hk6279 · Accepted Answer · 2014-10-07T07:58:00+0000

, , , Linkedlist H[i]==lowest. H[i]==lowest, reset . 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. while if- reset stack {3,1}, stack.peek() < H[i] if- (stack.peek() = H [6] = 3).

, if- if-else-if-else-if, H [i] i.

Manhattan cover horizon lacking some test cases

More articles: