2022.6.23今天你刷题了吗?
题目:
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] 是如上所述的 下一个更大元素
分析:
给定两个数组,例如
num1【1,2,3】,num2【1,2,4,3】,则num1的【1】对应num2的【2】,num1的2对应num2的【4】,num1的【3】则无对应,然后返回【2,4,-1】
也就是说对于数组一中的元素,我们要在数组2中去找是否存在一个元素满足下面条件
1.在num2下该必须是元素右方存在第一个一个元素
2.且该元素大于数组一中这个素
思路就是暴力求解,遍历两个数组,在第一层循环中去找num1的值,看第二层循环是否存在一个满足该要求的元素。
解析:
1.暴力求解
- class Solution {
- public:
- vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
- vector<int>vec;
- int flag = 0;
- for (auto i = 0; i < nums1.size(); ++i)
- {
- for (auto j = 0; j < nums2.size(); ++j)
- {
- if (nums1[i] == nums2[j])
- {
- flag = 1;
- }
- if (flag == 1&&nums1[i]<nums2[j])
- {
- vec.push_back(nums2[j]);
- flag = 0;
- break;
- }
- if (flag == 1 && nums1[i] >= nums2[j]&&j==nums2.size()-1)
- {
- vec.push_back(-1);
- flag = 0;
- break;
- }
- }
- }
- return vec;
- }
- };
2.单调栈
该类方法用于解决数组中下一个元素更大类型。
思想就是利用一个栈去维护一个从小到大排列的栈,然后把数据插入map中,再把map插入vector中(个人感觉还是很难)。其中如果在栈插入时遇到更大的值,就要进行出栈,这个方法还要多练!
- class Solution {
- public:
- vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
- unordered_map<int, int> hashmap;
- stack<int> st;
- for (int i = nums2.size() - 1; i >= 0; --i)
- {
- int num = nums2[i];
- while (!st.empty() && num >= st.top())
- {
- st.pop();
- }
- hashmap[num] = st.empty() ? -1 : st.top();
- st.push(num);
- }
- vector<int>res(nums1.size());
- for (auto i = 0; i < nums1.size(); ++i)
- {
- res[i] = hashmap[nums1[i]];
- }
- return res;
- }
- };