diff options
Diffstat (limited to 'other/next_greater_element2.cpp')
-rw-r--r-- | other/next_greater_element2.cpp | 43 |
1 files changed, 0 insertions, 43 deletions
diff --git a/other/next_greater_element2.cpp b/other/next_greater_element2.cpp deleted file mode 100644 index c6a8412..0000000 --- a/other/next_greater_element2.cpp +++ /dev/null @@ -1,43 +0,0 @@ -// 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 -} |