diff options
Merge branch 'main' of https://github.com/stoychoX/Data-structures-and-algorithms
1 files changed, 48 insertions, 0 deletions
| -rw-r--r-- | Practicum/pract06/solutions/Task 02.cpp | 48 |
diff --git a/Practicum/pract06/solutions/Task 02.cpp b/Practicum/pract06/solutions/Task 02.cpp new file mode 100644 index 0000000..6009d36 --- /dev/null +++ b/Practicum/pract06/solutions/Task 02.cpp @@ -0,0 +1,48 @@ +#include <string>
+#include <stack>
+#include <vector>
+
+class Solution
+{
+public:
+ std::vector<int> asteroidCollision(std::vector<int> &asteroids)
+ {
+ std::stack<int> stack;
+
+ for (int i = 0; i < asteroids.size(); ++i)
+ {
+ if (asteroids[i] > 0 || (stack.size() && stack.top() < 0))
+ {
+ stack.push(asteroids[i]);
+ continue;
+ }
+
+ bool addNeg = true;
+ while (stack.size() && stack.top() > 0 && stack.top() + asteroids[i] <= 0)
+ {
+ if (stack.top() + asteroids[i] == 0)
+ {
+ stack.pop();
+ addNeg = false;
+ break;
+ }
+ stack.pop();
+ }
+
+ if (addNeg && (stack.empty() || stack.top() < 0))
+ {
+ stack.push(asteroids[i]);
+ }
+ }
+
+ int idx = stack.size();
+ std::vector<int> result(idx);
+ while (stack.size())
+ {
+ result[--idx] = stack.top();
+ stack.pop();
+ }
+
+ return result;
+ }
+};
\ No newline at end of file |