Leetcode 496 Solution

This article provides solution to leetcode question 496 (next-greater-element-i)
Categories:
Tags:
Access this page by simply typing in "lcs 496" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/next-greater-element-i

Solution

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
        stack<int> s;
        vector<int> next_greaters(nums.size());
        unordered_map<int, int> pos;

        for (int i = nums.size() - 1; i >= 0; i--)
        {
            while (s.empty() == false && nums[i] >= s.top())
                s.pop();

            next_greaters[i] = s.empty() ? -1 : s.top();
            pos[nums[i]] = i;

            s.push(nums[i]);
        }

        vector<int> res;
        for (auto findnum : findNums)
        {
            int i = pos[findnum];
            res.push_back(next_greaters[i]);
        }

        return res;
    }
};