496. Next Greater Element I + 503. Next Greater Element II + 556. Next Greater Element III

▶ 给定一个数组与它的一个子列，对于数组中的一个元素，定义它右边第一个比他大的元素称为他的后继，求所给子列的后继构成的数组

▶ 第 496 题，规定数组最后一个元素即数组最大元素的后继均为 -1

● 自己的版本，12 ms，最快的解法算法与之相同

 1 class Solution
 2 {
 3 public:
 4     vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums)
 5     {        
 6         const int m = findNums.size(), n = nums.size();
 7         int i, j;
 8         unordered_map<int, int> table;
 9         vector<int> output;
10         for (i = 0; i < n; table[nums[i]] = i, i++);
11         for (i = 0; i < m; i++)
12         {
13             if (findNums[i] == nums[n - 1])
14             {
15                 output.push_back(-1);
16                 continue;
17             }
18             for (j = table[findNums[i]] + 1; j < n && nums[j] < findNums[i]; j++);
19             if (j == n)
20                 output.push_back(-1);
21             else
22                 output.push_back(nums[j]);
23         }
24         return output;
25     }
26 };

▶ 第 503 题，数组换成环状，只有数组最大元素的后继为 -1

● 自己的代码，124 ms，添加一个标记 mark 的线性搜索方法

 1 class Solution
 2 {
 3 public:
 4     vector<int> nextGreaterElements(vector<int>& nums)
 5     {
 6         const int n = nums.size();
 7         int i, mark;
 8         vector<int> output(n, -1);
 9         for (mark = 0; mark < n - 1 && nums[mark] <= nums[n - 1]; mark++);
10         if (mark < n - 1)   // 找到了某个位置，标记上，若 mark == n - 1，说明 nums[n - 1] 就是最大的
11             output[n - 1] = nums[mark];
12         for (i = n - 2; i >= 0; i--)
13         {
14             if (nums[i] < nums[i + 1])
15             {
16                 output[i] = nums[i + 1];
17                 mark = i + 1;
18             }
19             else
20             {
21                 for (; mark != i && nums[mark] <= nums[i]; mark = (mark + 1) % n);
22                 if (mark != i)
23                     output[i] = nums[mark];
24             }
25         }        
26         return output;
27     }
28 };

● 大佬的代码，111 ms

 1 class Solution
 2 {
 3 public:
 4     vector<int> nextGreaterElements(vector<int>& nums)
 5     {
 6         const int n = nums.size();
 7         int i, num, ind;
 8         stack<int> st;             // 栈维护 num 的单调递减的子列的下标，遇到较大的当前值的时候出栈，出到元素值大于当前值为止
 9         vector<int> result(n, -1);
10         for (i = 0; i < 2 * n; i++)// 扫描两趟，确保末尾的元素找到后继
11         {
12             for (num = nums[i % n]; !st.empty() && num > nums[st.top()]; ind = st.top(), st.pop(), result[ind] = num);
13                 // 若 num 较大，则把栈中的较小元素都指向 num
14             st.push(i % n); // 空栈，或者剩余部分的值大于当前值，将当前值压栈
15         }
16         return result;
17     }
18 };

● 大佬的代码，103 ms，两步走战略

 1 class Solution
 2 {
 3 public:
 4     vector<int> nextGreaterElements(vector<int> nums)
 5     {
 6         const int n = nums.size();
 7         if(n==0)
 8             return vector<int>();
 9         vector<int> res(n);
10         int i, maxValue, index, real; 
11         for (maxValue = nums[0], i = index = 0; i < n; i++)// 第一轮，将两种情况的第 k 元素进行标记：
12         {                                                  // ① nums[ k ] < nums[ k + 1 ]
13             if (nums[i] > maxValue)                        // ② nums[ k ] >= nums[ k + 1 ] ... nums[ k + m ] 且 nums[ k ] < nums[ k + m ]
14             {                                              // 注意第一轮结束时 index 等于数组最大元素的下标
15                 res[i - 1] = i;
16                 res[index] = i;
17                 maxValue = nums[i];
18                 index = i;
19             }
20         }        
21         for (res[index] = -1, i = index - 1; i > index - n; i--)// 将数组最大元素的输出值置 -1，从最大元素开始向左遍历数组
22         {
23             real = (i + n) % n;
24             if (res[real] != 0)
25                 continue;
26             res[real] = (real == n - 1 ? 0 : real + 1);// 让该元素的输出值初始化为它右边那个元素
27             for (; res[real] != -1 && nums[real] >= nums[res[real]]; res[real] = res[res[real]]);// 寻找该元素的真实输出值
28         }
29         for (i = 0; i < n; i++)// 将下标置换回元素的值
30         {
31             if (res[i] != -1)
32                 res[i] = nums[res[i]];
33         }
34         return res;
35     }
36 };

● 其他方法，枚举，时间复杂度 O(n²)