所有的LeetCode題解索引，可以看這篇文章——【算法和數據結構】LeetCode題解。

一、496、下一個更大元素 I

??思路分析：本題思路和【算法與數據結構】739、LeetCode每日溫度類似。如果用暴力破解法時間復雜度需要$O(m?n)$，其中$m$和$n$分別是兩個數組的長度。單調棧只需要$O(n+m)$的時間復雜度。相較于739題，本題需要找到nums1元素在nums2數組中的位置，那么我們可以利用unordered_map，查找和增刪效率是最高的【算法與數據結構】算法與數據結構知識點：

	unordered_map<int, int> umap; // key:下標元素，value：下標for (int i = 0; i < nums1.size(); i++) {umap[nums1[i]] = i;}

??然后利用739題的單調棧思路，遍歷nums2數組。每當當前遍歷元素大于棧頂元素，并且nums2數組的元素在nums1中存在（umap.count(nums2[st.top()]) > 0就是統計數量，大于零說明nums2[st.top()]元素存在），我們找到棧頂元素在nums1中的下標，在結果數組中根據下標修改其值：

	for (int i = 0; i < nums2.size(); i++) {			while (!st.empty() && nums2[i] > nums2[st.top()]) {if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在這個元素，count函數計算數量int index = umap[nums2[st.top()]]; // 根據map找到nums2[st.top()] 在 nums1中的下標result[index] = nums2[i];}st.pop();}st.push(i); // 插入數組的下標}

??程序如下：

// 496、下一個更大元素 I
class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> result(nums1.size(), -1);stack<int> st;unordered_map<int, int> umap; // key:下標元素，value：下標for (int i = 0; i < nums1.size(); i++) {umap[nums1[i]] = i;}for (int i = 0; i < nums2.size(); i++) {			while (!st.empty() && nums2[i] > nums2[st.top()]) {if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在這個元素，count函數計算數量int index = umap[nums2[st.top()]]; // 根據map找到nums2[st.top()] 在 nums1中的下標result[index] = nums2[i];}st.pop();}st.push(i); // 插入數組的下標}return result;}
};

復雜度分析：

• 時間復雜度： $O(n)$。
• 空間復雜度：$O(n)$。

二、503、下一個更大元素II

??思路分析：本題和496題不同之處在于從兩個數組變成一個數組，然后數組是環(huán)形數組。針對環(huán)形數組，我們要比較大小，可以將環(huán)形數組復制一份，兩個相同的數組擴充成一個新數組。然后在新數組上去做單調棧的操作。
??程序如下：

// 503、下一個更大元素II-版本一
class Solution2 {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> nums1(nums.begin(), nums.end()); // 拼接一個新的numsnums.insert(nums.end(), nums1.begin(), nums1.end());		vector<int> result(nums.size(), -1);	// 用新的nums大小來初始化result// 開始單調棧stack<int> st;st.push(0);for (int i = 1; i < nums.size(); i++) {while (!st.empty() && nums[i] > nums[st.top()]) {result[st.top()] = nums[i];st.pop();}st.push(i);}result.resize(nums.size() / 2);		// 最后再把結果集即result數組resize到原數組大小return result;}
};

??雖然這種寫法比較直觀，但是做了很多無用操作。resize函數是O(1)的操作，但擴充nums數組相當于多了一個O(n)的操作。其實也可以不擴充nums，而是在遍歷的過程中模擬走了兩邊nums。例如我們改變索引的上界，然后令其做取nums.size()模的操作。

// 503、下一個更大元素II-版本二
class Solution3 {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> result(nums.size(), -1);stack<int> st;for (int i = 0; i < nums.size() * 2; i++) {// 模擬遍歷兩邊nums，注意一下都是用i % nums.size()來操作while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {result[st.top()] = nums[i % nums.size()];st.pop();}st.push(i % nums.size());}return result;}
};

復雜度分析：

• 時間復雜度： $O(n)$。
• 空間復雜度：$O(n)$。

三、完整代碼

# include <iostream>
# include <vector>
# include <unordered_map>.
# include <stack>
using namespace std;// 496、下一個更大元素 I
class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> result(nums1.size(), -1);stack<int> st;unordered_map<int, int> umap; // key:下標元素，value：下標for (int i = 0; i < nums1.size(); i++) {umap[nums1[i]] = i;}for (int i = 0; i < nums2.size(); i++) {			while (!st.empty() && nums2[i] > nums2[st.top()]) {if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在這個元素，count函數計算數量int index = umap[nums2[st.top()]]; // 根據map找到nums2[st.top()] 在 nums1中的下標result[index] = nums2[i];}st.pop();}st.push(i); // 插入數組的下標}return result;}
};// 503、下一個更大元素II-版本一
class Solution2 {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> nums1(nums.begin(), nums.end()); // 拼接一個新的numsnums.insert(nums.end(), nums1.begin(), nums1.end());		vector<int> result(nums.size(), -1);	// 用新的nums大小來初始化result// 開始單調棧stack<int> st;st.push(0);for (int i = 1; i < nums.size(); i++) {while (!st.empty() && nums[i] > nums[st.top()]) {result[st.top()] = nums[i];st.pop();}st.push(i);}result.resize(nums.size() / 2);		// 最后再把結果集即result數組resize到原數組大小return result;}
};// 503、下一個更大元素II-版本二
class Solution3 {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> result(nums.size(), -1);if (nums.size() == 0) return result;stack<int> st;for (int i = 0; i < nums.size() * 2; i++) {// 模擬遍歷兩邊nums，注意一下都是用i % nums.size()來操作while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {result[st.top()] = nums[i % nums.size()];st.pop();}st.push(i % nums.size());}return result;}
};int main() {//vector<int> nums1 = { 4,1,2 };//vector<int> nums2 = { 1,3,4,2 };//Solution s1;//vector<int> result = s1.nextGreaterElement(nums1, nums2);vector<int> nums = { 1,2,3,4,3 };Solution2 s1;vector<int> result = s1.nextGreaterElements(nums);for (vector<int>::iterator i = result.begin(); i != result.end(); i++) {cout << *i << " ";}cout << endl;system("pause");return 0;
}

end