spider68

next greater element linked list

May 25th, 2020
181
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None | 0 0
  1. //Input: [1,2,1]
  2. //Output: [2,-1,2]
  3. //Explanation: The first 1's next greater number is 2;
  4. //The number 2 can't find next greater number;
  5. //The second 1's next greater number needs to search circularly, which is also 2.
  6.  
  7. <---------for vector------------>
  8. vector<int> nextGreaterElements(vector<int>& nums) {
  9.         int n = nums.size();
  10.         vector<int> next(n, -1);
  11.         stack<int> s; // index stack
  12.         for (int i = 0; i < n * 2; i++) {
  13.             int num = nums[i % n];
  14.             while (!s.empty() && nums[s.top()] < num) {
  15.                 next[s.top()] = num;
  16.                 s.pop();
  17.             }
  18.             if (i < n) s.push(i);
  19.         }  
  20.         return next;
  21.     }
  22.  
  23. <-----------linked list------->
  24. vector<int> nextLargerNodes(ListNode* head) {
  25.         vector<int> res, stack;
  26.         for (ListNode* node = head; node; node = node->next) {
  27.             while (stack.size() && res[stack.back()] < node->val) {
  28.                 res[stack.back()] = node->val;
  29.                 stack.pop_back();
  30.             }
  31.             stack.push_back(res.size());
  32.             res.push_back(node->val);
  33.         }
  34.         for (int i: stack) res[i] = 0;
  35.         return res;
  36.     }
Add Comment
Please, Sign In to add comment