Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //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.
- <---------for vector------------>
- vector<int> nextGreaterElements(vector<int>& nums) {
- int n = nums.size();
- vector<int> next(n, -1);
- stack<int> s; // index stack
- for (int i = 0; i < n * 2; i++) {
- int num = nums[i % n];
- while (!s.empty() && nums[s.top()] < num) {
- next[s.top()] = num;
- s.pop();
- }
- if (i < n) s.push(i);
- }
- return next;
- }
- <-----------linked list------->
- vector<int> nextLargerNodes(ListNode* head) {
- vector<int> res, stack;
- for (ListNode* node = head; node; node = node->next) {
- while (stack.size() && res[stack.back()] < node->val) {
- res[stack.back()] = node->val;
- stack.pop_back();
- }
- stack.push_back(res.size());
- res.push_back(node->val);
- }
- for (int i: stack) res[i] = 0;
- return res;
- }
Add Comment
Please, Sign In to add comment