@@ -28,7 +28,7 @@ Output: [2,3,4,-1,4]
28
28
------------------------------------------------------------------------------------
29
29
```
30
30
31
- ## Solution 1
31
+ ## Solution 1: Brute Force
32
32
This problem can be solved using ** Brute Force** . But if the ` nums.length ` is much greater, the solution will time out.
33
33
Then We need to use a more efficient algorithm.
34
34
@@ -38,11 +38,51 @@ Detailed solutions will be given later, and now only the best practices in 7 lan
38
38
* Time: ` O(n * n) ` .
39
39
* Space: ` O(n) ` .
40
40
41
- ## Solution 2: More efficient algorithm via "Monotonic Stack"
41
+ ## Solution 2: Monotonic Stack Algorithm (more efficient)
42
42
This solution will reduce the time complexity to ** O(n)** .
43
43
44
- A similar issue is [ Next Greater Element I] ( 496-next-greater-element-i.md ) .
45
- You can read it first, then checkout the ` Python ` section for the code.
44
+ A similar issue is [ Next Greater Element I] ( 496-next-greater-element-i.md ) , you can read it first.
45
+
46
+ Checkout the ` Python ` section bellow to view the code.
47
+
48
+ ## Python
49
+ ### Solution 2: Monotonic Stack
50
+ ``` python
51
+ # This is a better test case:
52
+ # [2, 5, 3, 2, 4, 1] for `nums`
53
+ # [2, 5, 3, 2, 4, 1, 2, 5, 3, 2, 4] for `extended_nums`
54
+
55
+ class Solution :
56
+ def nextGreaterElements (self , nums : List[int ]) -> List[int ]:
57
+ extended_nums = nums + nums[:- 1 ]
58
+ index_stack = []
59
+ result = [- 1 ] * len (extended_nums)
60
+
61
+ for i, num in enumerate (extended_nums):
62
+ while index_stack and extended_nums[index_stack[- 1 ]] < num:
63
+ result[index_stack.pop()] = num
64
+
65
+ index_stack.append(i)
66
+
67
+ return result[:len (nums)]
68
+ ```
69
+
70
+ ### Solution 1: Brute Force
71
+ ``` python
72
+ class Solution :
73
+ def nextGreaterElements (self , nums : List[int ]) -> List[int ]:
74
+ results = [- 1 ] * len (nums)
75
+ nums2 = nums + nums
76
+
77
+ for i, num1 in enumerate (nums):
78
+ for j in range (i + 1 , len (nums2)):
79
+ if nums2[j] > num1:
80
+ results[i] = nums2[j]
81
+ break
82
+
83
+ return results
84
+ ```
85
+
46
86
47
87
## C#
48
88
``` c#
@@ -71,44 +111,6 @@ public class Solution
71
111
}
72
112
```
73
113
74
- ## Python
75
- ### Solution 1: Brute Force
76
- ``` python
77
- class Solution :
78
- def nextGreaterElements (self , nums : List[int ]) -> List[int ]:
79
- results = [- 1 ] * len (nums)
80
- nums2 = nums + nums
81
-
82
- for i, num1 in enumerate (nums):
83
- for j in range (i + 1 , len (nums2)):
84
- if nums2[j] > num1:
85
- results[i] = nums2[j]
86
- break
87
-
88
- return results
89
- ```
90
-
91
- ### Solution 2: Monotonic Stack
92
- ``` python
93
- # This is a better test case:
94
- # [2, 5, 3, 2, 4, 1] for `nums`
95
- # [2, 5, 3, 2, 4, 1, 2, 5, 3, 2, 4] for `extended_nums`
96
-
97
- class Solution :
98
- def nextGreaterElements (self , nums : List[int ]) -> List[int ]:
99
- extended_nums = nums + nums[:- 1 ]
100
- index_stack = []
101
- result = [- 1 ] * len (extended_nums)
102
-
103
- for i, num in enumerate (extended_nums):
104
- while index_stack and extended_nums[index_stack[- 1 ]] < num:
105
- result[index_stack.pop()] = num
106
-
107
- index_stack.append(i)
108
-
109
- return result[:len (nums)]
110
- ```
111
-
112
114
## Java
113
115
``` java
114
116
class Solution {
0 commit comments