Leetcode 503. Next Greater Element II JAVA語言

1

2

3

4

5

6

<code>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.</code>

<code>Example 1:</code>

<code>Input: [1,2,1]Output: [2,-1,2]Explanation: The first 1's next greater number is 2; </code>

<code>The number 2 can't find next greater number; </code>

<code>The second 1's next greater number needs to search circularly, which is also 2.</code>

<code>Note: The length of given array won't exceed 10000.</code>

題意:給一個循環數組，求解其next greater number：第一個比其大的數。

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

<code>public</code> <code>class</code> <code>Solution {</code>

<code>    </code><code>////這個思路是直接double數組，把原來的循環簡化了。貌似還有用棧的。再看看。</code>

<code>    </code><code>public</code> <code>int</code><code>[] nextGreaterElements(</code><code>int</code><code>[] nums) {</code>

<code>        </code><code>if</code><code>(nums.length==</code><code>1</code><code>){</code>

<code>            </code><code>nums[</code><code>0</code><code>]=-</code><code>1</code><code>;</code>

<code>            </code><code>return</code> <code>nums;</code>

<code>        </code><code>}</code>

<code>        </code><code>int</code><code>[] newnums=</code><code>new</code> <code>int</code><code>[nums.length*</code><code>2</code><code>];</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i=</code><code>0</code><code>;i&lt;newnums.length;i++){</code>

<code>            </code><code>newnums[i]=nums[i%nums.length];</code>

<code>        </code><code>// for(int i=0;i&lt;nums.length;i++){</code>

<code>        </code><code>//     newnums[i]=nums[i];</code>

<code>        </code><code>// }</code>

<code>        </code><code>// int index=0;</code>

<code>        </code><code>// for(int i=nums.length;i&lt;newnums.length;i++){</code>

<code>        </code><code>//     newnums[i]=nums[index++];</code>

<code>        </code><code>// for(int i=0;i&lt;nums.length*2;i++){</code>

<code>        </code><code>//     System.out.println(newnums[i]+"  ");</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i=</code><code>0</code><code>;i&lt;nums.length;i++)</code>

<code>            </code><code>for</code><code>(</code><code>int</code> <code>j=i+</code><code>1</code><code>;j&lt;i+nums.length;j++)</code>

<code>            </code><code>if</code><code>(newnums[j]&gt;newnums[i]){</code>

<code>                </code><code>nums[i]=newnums[j];</code>

<code>                </code><code>break</code><code>;</code>

<code>            </code><code>}</code><code>else</code><code>{</code>

<code>                </code><code>nums[i]=-</code><code>1</code><code>;</code>

<code>            </code><code>}</code>

<code>        </code><code>return</code> <code>nums;</code>

<code>    </code><code>}</code>

<code>}</code>

PS:聽群裡大神說把數組直接double一下，然後就可以簡化了，【好厲害】。然後就是暴力搜尋了。。。。。。。。貌似還有棧！

棧的話，若目前元素小于等于棧頂元素，直接入棧。若大于棧頂元素，即将所有小于該元素的值出站，并作為=他們的next greater number。再來一次循環，隻出棧，看看能不能找到比他大的元素。最後看看棧裡的元素就是最大值，直接設為-1

本文轉自 努力的C 51CTO部落格，原文連結:http://blog.51cto.com/fulin0532/1901699