leetcode链接：
503. 下一个更大元素 II
题目分析
方案一
既然说了是循环，那就之执行两遍
只执行一次循环的 时候，必然会有数组后面的数据被保存到堆栈中无法正常弹出，因此，循环执行两次，两次执行之后，放在堆栈里面的只有最大值了，所以也就可以得到最终的相关结果了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int[] nextGreaterElements(int[] nums) {
int[] result = new int[nums.length];
Arrays.fill(result, -1);
Deque<Integer> deque = new ArrayDeque<>();
int length = nums.length;
for (int i = 0; i < 2 * nums.length; i++) {
while (!deque.isEmpty() && nums[deque.peek()] < nums[i % length]) {
Integer pop = deque.pop();
result[pop] = nums[i % length];
}
deque.push(i % length);
}
return result;
}
}
|
结果
解答成功:
执行耗时:5 ms,击败了94.04% 的Java用户
内存消耗:43.4 MB,击败了60.91% 的Java用户
分析
时间复杂度：
O( n )
空间复杂度：
O( n )
代码随想录
https://programmercarl.com/0503.%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E5%85%83%E7%B4%A0II.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC
如何处理循环数组。
相信不少同学看到这道题，就想那我直接把两个数组拼接在一起，然后使用单调栈求下一个最大值不就行了！
确实可以！
将两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以了。
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
26
27
28
29
30
|
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> nums1(nums.begin(), nums.end());
nums.insert(nums.end(), nums1.begin(), nums1.end());
vector<int> result(nums.size(), -1);
if (nums.size() == 0) return result;
stack<int> st;
st.push(0);
for (int i = 1; i < nums.size(); i++) {
if (nums[i] < nums[st.top()]) st.push(i);
else if (nums[i] == nums[st.top()]) st.push(i);
else {
while (!st.empty() && nums[i] > nums[st.top()]) {
result[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
}
result.resize(nums.size() / 2);
return result;
}
};
|
这种写法确实比较直观，但做了很多无用操作，例如修改了nums数组，而且最后还要把result数组resize回去。
resize倒是不费时间，是O(1)的操作，但扩充nums数组相当于多了一个O(n)的操作。
其实也可以不扩充nums，而是在遍历的过程中模拟走了两边nums。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> result(nums.size(), -1);
if (nums.size() == 0) return result;
stack<int> st;
st.push(0);
for (int i = 1; i < nums.size() * 2; i++) {
if (nums[i % nums.size()] < nums[st.top()]) st.push(i % nums.size());
else if (nums[i % nums.size()] == nums[st.top()]) st.push(i % nums.size());
else {
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;
}
};
|
可以版本二不仅代码精简了，也比版本一少做了无用功！
最后在给出 单调栈的精简版本，即三种情况都做了合并的操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
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++) {
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;
}
};
|
JAVA版本如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int[] nextGreaterElements(int[] nums) {
if(nums == null || nums.length <= 1) {
return new int[]{-1};
}
int size = nums.length;
int[] result = new int[size];
Arrays.fill(result,-1);
Stack<Integer> st= new Stack<>();
for(int i = 0; i < 2*size; i++) {
while(!st.empty() && nums[i % size] > nums[st.peek()]) {
result[st.peek()] = nums[i % size];
st.pop();
}
st.push(i % size);
}
return result;
}
}
|
官方题解
https://leetcode.cn/problems/next-greater-element-ii/solution/xia-yi-ge-geng-da-yuan-su-ii-by-leetcode-bwam/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> ret(n, -1);
stack<int> stk;
for (int i = 0; i < n * 2 - 1; i++) {
while (!stk.empty() && nums[stk.top()] < nums[i % n]) {
ret[stk.top()] = nums[i % n];
stk.pop();
}
stk.push(i % n);
}
return ret;
}
};
作者：LeetCode-Solution
链接：https:
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|
