Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

[刷题]下一个更大元素问题

自然语言不理解 2020-01-09 09:53:20 阅读数:18 评论数:0 点赞数:0 收藏数:0

Leetcode 496 下一个更大元素Ⅰ

问题描述

对一个数组的每一个元素,找到当前位置之后第一个比当前元素大的元素
[2,1,3,4] ==[Next Greater Number Array]==> [3,3,4,-1]

解法思路

1.如果我们从前往后考虑这个问题,最直接的思路,对每个位置我们比较当前元素和之后所有元素,遇到第一个比自己大的,即为所求。这种暴力法的时间复杂度为O(N x N)
2.那么我们是否可以减少一些比较呢?当然是可以的,我们从后往前考虑这个问题。我们用一个有序栈保存比当前位置大的元素(并不是所有比当前大的)。如[2,1,4,3,6,7] 当遍历到1时栈为[4.6,7],也就是对于一个位置只能看到第一个比自己大的元素。遍历到一个元素时,比较栈顶元素和自己,比自己小的元素都被刨除(栈中比自己小的元素都弹出),直到栈顶元素比自己大,记录这个元素(或做一些相应的操作)。由于不知道下一个遍历的元素比自己大还是小,所以把自己也放入栈中,遍历下一个元素。

通用代码
public int[] NextGreaterNumber(int[] T) {
Stack<Integer> stack = new Stack<>();
int[] res = new int[T.length];
for(int i=T.length-1;i>=0;i--){
while (!stack.empty()&&stack.peek()<=T[i]){
stack.pop();
}
if(stack.empty()) res[i] = -1;
else {
res[i] = stack.peek();
}
stack.push(T[i]);
}
return res;
}
版权声明
本文为[自然语言不理解]所创,转载请带上原文链接,感谢
https://segmentfault.com/a/1190000021530271