From 51d955fbdada4400c8efd504d637b4ece6fcee22 Mon Sep 17 00:00:00 2001
From: Stoycho Kyosev <stoycho.kk@gmail.com>
Date: Wed, 12 Oct 2022 15:42:41 +0300
Subject: add seminar02

---
 Seminar02/task04.cpp | 47 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 47 insertions(+)
 create mode 100644 Seminar02/task04.cpp

(limited to 'Seminar02/task04.cpp')

diff --git a/Seminar02/task04.cpp b/Seminar02/task04.cpp
new file mode 100644
index 0000000..91207a0
--- /dev/null
+++ b/Seminar02/task04.cpp
@@ -0,0 +1,47 @@
+#include<iostream>
+#include<stack>
+#include<vector>
+
+class firstLeftGreaterElement {
+private:
+    std::vector<int> data;
+
+    void init(const std::vector<int>& v) {
+        std::stack<int> monotonicStack;
+
+        data.resize(v.size());
+
+        for (size_t i = 0; i < v.size(); i++) {
+            while(!monotonicStack.empty() && monotonicStack.top() < v[i]) {
+                monotonicStack.pop();
+            }
+
+            data[i] = monotonicStack.empty() ? -1 : monotonicStack.top();
+            monotonicStack.push(v[i]);
+        }
+    }
+
+public:
+    firstLeftGreaterElement(const std::vector<int>& v) {
+        init(v);
+    }
+
+    int getFirstLeftGreaterElement(size_t idx) const {
+        return data[idx];
+    }
+};
+
+int main() {
+    std::vector<int> example {4, 7, 2, 3, 12, 6, 4, 13};
+    std::vector<int> example2 {1, 4, 3, 8, 12, 7};
+
+    firstLeftGreaterElement f(example);
+    firstLeftGreaterElement s(example2);
+
+    for (size_t i = 0; i < example.size(); i++)
+        std::cout << f.getFirstLeftGreaterElement(i) << " ";
+
+    std::cout << std::endl;
+
+    std::cout << s.getFirstLeftGreaterElement(0) << " " << s.getFirstLeftGreaterElement(2) << " " << s.getFirstLeftGreaterElement(5);
+}
\ No newline at end of file
-- 
cgit v1.3.1-23-gd82d