跳转至

496/503. 下一个更大元素 I/II

力扣链接(简单)：https://leetcode.cn/problems/next-greater-element-i

力扣链接(中等)：https://leetcode.cn/problems/next-greater-element-ii

496. 下一个更大元素 I

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

示例 1：

Text Only
1
2
3
4
5
6
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

示例 2：

Text Only
1
2
3
4
5
输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

提示：

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • nums1 和 nums2 中所有整数 互不相同
  • nums1 中的所有整数同样出现在 nums2 中

进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

个人题解

题目描述并不清晰，说简单点就是在 nums1 中的元素，首先找到其在 nums2 中的对应位置，然后在该位置往后找比该元素更大的第一个元素，写入对应的结果中。

题目中提到，两个数组均为没有重复元素的数组，为了在遍历过程中，不用重复对另一个数组进行遍历，考虑使用哈希表对 value-index 映射。又因为，本题是在 nums2 中寻找更大元素，所以显然是对 nums2 进行遍历，然后判断遍历元素是否存在于 nums1 存在则将其写入结果。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> umap;
        stack<int> st;
        vector<int> result(nums1.size(), -1);

        // 由于要返回在 nums2 中的更大元素，所以后续遍历的是 nums2 
        // 提前对 nums1 元素下标做哈希，后续可以直接判断 nums2 中某元素是否存在于 nums1
        for(int i = 0; i < nums1.size(); i++) {
            umap[nums1[i]] = i;
        }

        st.push(0);
        for(int i = 1; i < nums2.size(); i++) {
            while(!st.empty() && nums2[st.top()] < nums2[i]) {
                if(umap.count(nums2[st.top()])) result[umap[nums2[st.top()]]] = nums2[i];
                st.pop();
            }
            st.push(i);
        }

        return result;
    }
};

503. 下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

示例 1:

Text Only
1
2
3
4
5
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

示例 2:

Text Only
1
2
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示:

  • 1 <= nums.length <= 104
  • -109 <= nums[i] <= 109

个人题解

对于循环数组来说，有一种比较简单的办法就是将同一个数组拼接一次，如将 ABC 拼接为 ABCABC，这样从任意位置遍历一遍都相当于遍历了原数组中的所有元素，缺点是时间复杂度会增加 \(O(N)\)，主要来源于拼接数组时的 insert 函数，另外，拼接还会产生一个空间复杂度为 \(O(2N) \sim O(N)\) 的数组。

还有一种办法就是将遍历长度扩充到循环数组长度的两倍，然后对 index 进行取模操作，即可完成循环遍历。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> st;
        vector<int> result(nums.size(), -1);

        st.push(0);
        // 由于是循环数组，所以遍历到末尾后还需要从头开始继续遍历到当前位置
        // i < nums.size() * 2
        for(int i = 1; i < nums.size() * 2; i++) {
            while(!st.empty() && nums[st.top()] < nums[i % nums.size()]) {
                result[st.top()] = nums[i % nums.size()];
                st.pop();
            }
            st.push(i % nums.size());
        }

        return result;
    }
};