代码随想录算法训练营第四十五天| 503.下一个更大元素II 42. 接雨水 -JZTXT

503.下一个更大元素II

要求：

数组是环，需要找到下一个最大的元素

思路1：

先作为直线遍历，然后没有的节点，放到首部，再找比他大的节点

注意：头节点

代码：

 1 // 要求：返回循环数组中下一个更大的数字步数
 2 // 思路：先不循环遍历，
 3 // 然后对每个-1节点，以他为起始，放到数组的开头，计算有几个，仅计算一遍
 4 //
 5 vector<int> nextGreaterElements_complicate(vector<int>& nums) {
 6     vector<int> result(nums.size(), INT_MIN);
 7     stack<int> st;
 8 
 9     st.push(0);
10     for (int i = 1; i < nums.size(); i++)
11     {
12         if (nums[i] <= nums[st.top()])
13         {
14             st.push(i);
15         }
16         else
17         {
18             while (!st.empty() && nums[i] > nums[st.top()])
19             {
20                 result[st.top()] = nums[i];
21                 st.pop();
22             }
23             st.push(i);
24         }
25     }
26 
27     for (int i = 1; i < nums.size(); i++)
28     {
29         if (result[i] == INT_MIN)
30         {
31             cout << result[i] << endl;
32             for (int j = 0; j < i; j++)
33             {
34                 if (nums[i] < nums[j])
35                 {
36                     result[i] = nums[j];
37                     break;
38                 }
39             }
40         }
41         if (result[i] == INT_MIN)
42         {
43             result[i] = -1;
44         }
45     }
46 
47     if(result[0]== INT_MIN)result[0] = -1;
48 
49     return result;
50 }

思路2：

模拟遍历两次，也就是重复的把前面的节点，放到后面节点的后面

代码：

 1 // 新思路：模拟走两边，这样就可以把前面的节点放到后面的节点的后边
 2 //
 3 vector<int> nextGreaterElements(vector<int>& nums) {
 4     vector<int> result(nums.size(),-1);
 5     stack<int>st;
 6 
 7     st.push(0);
 8     for (int i = 1; i < nums.size() * 2; i++)
 9     {
10         if (nums[i % nums.size()] <= nums[st.top()])
11         {
12             st.push(i % nums.size());
13         }
14         else
15         {
16             while (!st.empty() && nums[i % nums.size()] > nums[st.top()])
17             {
18                 result[st.top()] = nums[i % nums.size()];
19                 st.pop();
20             }
21 
22             st.push(i % nums.size());
23         }
24     }
25 
26     return result;
27 }