✅ Решение задачи 1642Time: O(n log(k))
Space: O(k)
💡 Идея🟦Проходим по массиву и на каждом шаге:
➖оцениваем разницу в высоте между следующим зданием и текущим —
climb➖если
climb > 0, значит нужно каким-то образом преодолеть подъём, для чего всегда используем лестницы и добавляем текущий подъем в
PriorityQueue➖но, если размер очереди стал больше
ladders, значит лестницы закончились, и пора использовать кирпичи вместо самого маленького подъема, который мы достаем из очереди
➖если после этого кирпичей стало меньше 0, значит все ресурсы закончились и можно возвращать текущий индекс
🟦В результате получаем оптимальное использование ресурсов, жадно используя лестницы для самых больших подъемов, а кирпичи — для меньших
👩💻 Java Algo |
#solution1642