aboutsummaryrefslogtreecommitdiff
path: root/other/next_greater_element2.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/next_greater_element2.cpp')
-rw-r--r--other/next_greater_element2.cpp43
1 files changed, 43 insertions, 0 deletions
diff --git a/other/next_greater_element2.cpp b/other/next_greater_element2.cpp
new file mode 100644
index 0000000..c6a8412
--- /dev/null
+++ b/other/next_greater_element2.cpp
@@ -0,0 +1,43 @@
+// 503. Next Greater Element II
+#include "leetcode.h"
+
+/*
+ * given a circular integer array 'nums' (ie. the next element 'nums[nums.length
+ * - 1]' is 'nums[0]') return the next greater number for every element in
+ * 'nums'. the next greater number of a number 'x' is the first greater number
+ * to its traversing-order next in the array, which means you could search
+ * circularly to find its next greater number. if it doesn't exist, return -1
+ */
+
+class Solution {
+public:
+ vector<int> nextGreatestElements(vector<int> &nums) {
+ int n = nums.size();
+ nums.resize(n * 2);
+ for (int i = n; i < n * 2; i++)
+ nums[i] = nums[i - n];
+ vector<int> ans(n, -1);
+ stack<int> s;
+ for (int i = 0; i < n * 2; i++) {
+ int elem = nums[i];
+ while (!s.empty() && elem > nums[s.top()]) {
+ if (s.top() >= n)
+ s.top() = s.top() - n;
+ ans[s.top()] = elem;
+ s.pop();
+ }
+ s.push(i);
+ }
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<int> n1 = {1, 2, 1}, n2 = {1, 2, 3, 4, 3};
+ for (auto i : obj.nextGreatestElements(n1))
+ printf("%d ", i); // expect: 2 -1 2
+ printf("\n");
+ for (auto i : obj.nextGreatestElements(n2))
+ printf("%d ", i); // expect: 2 3 4 -1 4
+}