496/503-下一个更大元素

LeetCode 496. Next Greater Element I

LeetCode-496

You are given two integer arrays nums1 and nums2 both of unique elements, where nums1 is a subset of nums2.

Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, return -1 for this number.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation:
For number 4 , you cannot find the next greater number for it in the second array, so output -1.
For number 1 , the next greater number for it in the second array is 3.
For number 2 , there is no next greater number for it in the second array, so output -1.

method: 单调栈+哈希表

从前往后遍历，如果nums[i]比栈顶元素大，就把栈顶元素出栈，同时也表明栈顶元素的右边第一个比它大的数就是nums[i]，注意是while循环

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    stack<int> st;
    map<int, int> hash;
    for (int i = 0; i < nums2.size(); ++i) {
        while (!st.empty() && nums2[i] > st.top()) {
            hash[st.top()] = nums2[i];
            st.pop();
        }
        st.push(nums2[i]);
    }
    vector<int> res();
    for (auto n : nums1) {
        res.push_back(hash[n] ? hash[n] : -1);
    }
    return res;
}

---

LeetCode 503. Next Greater Element II

LeetCode-503

Given a circular integer array nums (i.e., the next element of 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 for this number.

Example 1:

Input: nums = [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.

method: 单调栈

注意：循环数组的写法，扩大一倍，取元素的时候对index取模

大于nums.size()的就不需要再入栈了

vector<int> nextGreaterElements(vector<int>& nums) {
    stack<int> st;
    int n = nums.size();
    vector<int> ret(n, -1);
    for (int i = 0; i < n * 2; ++i) {
        int num = nums[i % n];  // 下标要对size取模
        while (!st.empty() && num > nums[st.top()]) {
            ret[st.top()] = num;
            st.pop();
        }
        if (i < n) st.push(i);  // 小于size才需要入栈
    }
    return ret;
}