Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitd922f34

Browse files
committed
503-next-greater-element-ii.md AddedMonotonic Stack solution.
1 parent777e938 commitd922f34

File tree

2 files changed

+52
-4
lines changed

2 files changed

+52
-4
lines changed

‎en/1-1000/503-next-greater-element-ii.md

Lines changed: 26 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -38,9 +38,11 @@ Detailed solutions will be given later, and now only the best practices in 7 lan
3838
* Time:`O(n * n)`.
3939
* Space:`O(n)`.
4040

41-
##Solution 2: More efficient algorithm
41+
##Solution 2: More efficient algorithm via "Monotonic Stack"
4242
This solution will reduce the time complexity to**O(n)**.
43-
Please read[Next Greater Element I](496-next-greater-element-i.md).
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.
4446

4547
##C#
4648
```c#
@@ -70,6 +72,7 @@ public class Solution
7072
```
7173

7274
##Python
75+
###Solution 1: Brute Force
7376
```python
7477
classSolution:
7578
defnextGreaterElements(self,nums: List[int]) -> List[int]:
@@ -85,6 +88,27 @@ class Solution:
8588
return results
8689
```
8790

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+
classSolution:
98+
defnextGreaterElements(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, numinenumerate(extended_nums):
104+
while index_stackand 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+
88112
##Java
89113
```java
90114
classSolution {

‎zh/1-1000/503-next-greater-element-ii.md

Lines changed: 26 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -38,9 +38,11 @@ Detailed solutions will be given later, and now only the best practices in 7 lan
3838
* Time:`O(n * n)`.
3939
* Space:`O(n)`.
4040

41-
##Solution 2: More efficient algorithm
41+
##Solution 2: More efficient algorithm via "Monotonic Stack"
4242
This solution will reduce the time complexity to**O(n)**.
43-
Please read[Next Greater Element I](496-next-greater-element-i.md).
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.
4446

4547
##C#
4648
```c#
@@ -70,6 +72,7 @@ public class Solution
7072
```
7173

7274
##Python
75+
###Solution 1: Brute Force
7376
```python
7477
classSolution:
7578
defnextGreaterElements(self,nums: List[int]) -> List[int]:
@@ -85,6 +88,27 @@ class Solution:
8588
return results
8689
```
8790

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+
classSolution:
98+
defnextGreaterElements(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, numinenumerate(extended_nums):
104+
while index_stackand 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+
88112
##Java
89113
```java
90114
classSolution {

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp