Next Greater Element I题目描述代码实现Next Greater Element II题目描述代码实现
Example 1: Input: nums1 = [4,1,2], nums2 = [1,3,4,2]. Output: [-1,3,-1] Explanation: For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1. For number 1 in the first array, the next greater number for it in the second array is 3. For number 2 in the first array, there is no next greater number for it in the second array, so output -1
Example 2: Input: nums1 = [2,4], nums2 = [1,2,3,4]. Output: [3,-1] Explanation: For number 2 in the first array, the next greater number for it in the second array is 3. For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
Note:All elements in nums1 and nums2 are unique.The length of both nums1 and nums2 would not exceed 1000.很简单就可以想到O(n^2)的算法：
class Solution {public: vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) { int f_len = findNums.size(); int n_len = nums.size(); vector<int> res; for(int i = 0; i < f_len; i++) { bool flg = false; for(int j = 0; j < n_len; j++) { if(findNums[i] == nums[j]) flg = true; if(flg && nums[j] > findNums[i]) { res.push_back(nums[j]); flg = false; break; } } if(flg) res.push_back(-1); } return res; }};但是这种方法效率低下。 修改一下算法，我们如果可以找到其中的对应关系。
class Solution {public: vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) { int n_len = nums.size(); vector<int> res, s(n_len); unordered_map<int, int> next; // map: n in nums -> next greater in nums for (int i=0, j=0; j < n_len; s[i++] = nums[j++]) while (i && s[i-1] < nums[j]) next[s[--i]] = nums[j]; for (int n:findNums) res.push_back(next.count(n)? next[n] : -1); return res; }};使用栈的方法：
class Solution {public: vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) { stack<int> s; unordered_map<int, int> m; for (int n : nums) { while (s.size() && s.top() < n) { m[s.top()] = n; s.pop(); } s.push(n); } vector<int> ans; for (int n : findNums) ans.push_back(m.count(n) ? m[n] : -1); return ans; }};Given a circular array (the next element of the last element is the first element of the array), PRint the Next Greater Number for every element. 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, output -1 for this number.
Example 1:Input: [1,2,1]Output: [2,-1,2]Explanation: The first 1's next greater number is 2; The number 2 can't find next greater number; The second 1's next greater number needs to search circularly, which is also 2.Note: The length of given array won't exceed 10000.这里其实最重要的就是解决数字会重复出现的问题。这个时候不能使用map，所以我使用vector+pair的形式来实现可以有重复元素的映射。
class Solution {public: vector<int> nextGreaterElements(vector<int>& nums) { stack<int> stk; int n_len = nums.size(); int c_len = (n_len << 1) - 1; vector<pair<int, int>> vp(n_len); vector<int>res; for(int i = 0; i < c_len; i++) { int rind; int ind = rind = i%n_len, tmp = nums[ind]; while(!stk.empty() && stk.top() < tmp) { ind = (ind == 0)?n_len-1:ind-1; int flg = 0; while(vp[ind].first) ind = (ind - 1 >= 0)?ind-1:n_len-1; vp[ind].second = tmp; vp[ind].first = 1; stk.pop(); } if(!vp[rind].first) stk.push(tmp); } for(auto n:vp) res.push_back(n.first?n.second:-1); return res; }};新闻热点
疑难解答
