Это подсказка:
Вы собираетесь построить каменную стену. Стена должна быть прямой, длиной N метров и постоянной толщиной; однако в разных местах он должен иметь разную высоту. Высота стены задается массивом H с нулевым индексом из N положительных целых чисел.
H — высота стены от I до I+1 метров справа от ее левого конца. В частности, H[0] — это высота левого конца стены, а H[N−1] — высота правого конца стены.
Стена должна быть построена из кубовидных каменных блоков (то есть все стороны таких блоков прямоугольные). Ваша задача — вычислить минимальное количество блоков, необходимое для строительства стены.
Напишите функцию, которая, учитывая массив H с нулевым индексом, равный N< /code> положительные целые числа, определяющие высоту стены, возвращают минимальное количество блоков, необходимых для ее строительства.
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. На рисунке показано одно возможное расположение семи блоков.
Предположим, что:< /p>
- 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 stack = new LinkedList();
int count = 1;
int lowest = H[0];
stack.push(H[0]);
if(H.length == 1){
return 1;
}
else{
for(int i = 1; i H[i-1]){
stack.push(H);
count++;
}
if(H < lowest){
while(stack.size() > 0){
stack.pop();
}
stack.push(H);
lowest = H;
count++;
}
if(H < H[i-1] && H > lowest){
while(stack.size() > 0 && stack.peek() > H){
stack.pop();
}
if(stack.size() > 0 && stack.peek() < H){
stack.push(H);
count++;
}
}
}
}
return count;
}
}
Подробнее здесь: https://stackoverflow.com/questions/262 ... test-cases
