|
1
2
3
4
5
6
|
Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.
Example 1:
Input: [1,2,1]Output: [2,-1,2]Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number;
The second 1's next greater number needs to search circularly, which is also 2.
Note: The length of given array won't exceed 10000.
|
题意:给一个循环数组，求解其next greater number：第一个比其大的数。
|
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
31
32
|
public
class
Solution {
////这个思路是直接double数组，把原来的循环简化了。貌似还有用栈的。再看看。
public
int
[] nextGreaterElements(
int
[] nums) {
if
(nums.length==
1
){
nums[
0
]=-
1
;
return
nums;
}
int
[] newnums=
new
int
[nums.length*
2
];
for
(
int
i=
0
;i<newnums.length;i++){
newnums[i]=nums[i%nums.length];
}
// for(int i=0;i<nums.length;i++){
// newnums[i]=nums[i];
// }
// int index=0;
// for(int i=nums.length;i<newnums.length;i++){
// newnums[i]=nums[index++];
// }
// for(int i=0;i<nums.length*2;i++){
// System.out.println(newnums[i]+" ");
// }
for
(
int
i=
0
;i<nums.length;i++)
for
(
int
j=i+
1
;j<i+nums.length;j++)
if
(newnums[j]>newnums[i]){
nums[i]=newnums[j];
break
;
}
else
{
nums[i]=-
1
;
}
return
nums;
}
}
|
PS:听群里大神说把数组直接double一下，然后就可以简化了，【好厉害】。然后就是暴力搜索了。。。。。。。。貌似还有栈！
栈的话，若当前元素小于等于栈顶元素，直接入栈。若大于栈顶元素，即将所有小于该元素的值出站，并作为=他们的next greater number。再来一次循环，只出栈，看看能不能找到比他大的元素。最后看看栈里的元素就是最大值，直接设为-1
本文转自 努力的C 51CTO博客，原文链接:http://blog.51cto.com/fulin0532/1901699
