/
DeC2018
/
0042
Обзор
Документация
Войти
/
DeC2018
/
0042
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
main.cpp
40 строк
1 KB
Den
create main.cpp
26 янв 2025, 00:38
26 янв 2025, 00:38
9035b96
Код
Авторство
О чём код?
#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution { public: int trap(vector<int>& height) { const int n = height.size(); int ans = 0; vector<int> l(n); // l[i] := max(height[0..i]) vector<int> r(n); // r[i] := max(height[i..n)) for (int i = 0; i < n; ++i) l[i] = i == 0 ? height[i] : max(height[i], l[i - 1]); for (int i = n - 1; i >= 0; --i) r[i] = i == n - 1 ? height[i] : max(height[i], r[i + 1]); for (int i = 0; i < n; ++i) ans += min(l[i], r[i]) - height[i]; return ans; } }; int main() { Solution solution; vector<int> height1 = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}; cout << "Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]" << endl; cout << "Output: " << solution.trap(height1) << endl; vector<int> height2 = {4, 2, 0, 3, 2, 5}; cout << "Input: height = [4,2,0,3,2,5]" << endl; cout << "Output: " << solution.trap(height2) << endl; return 0; }