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

Commit1f50c40

Browse files
authored
Add Next Greater and Next Smaller Elements using Stack (TheAlgorithms#2858)
1 parentbc6de37 commit1f50c40

File tree

2 files changed

+138
-0
lines changed

2 files changed

+138
-0
lines changed
Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
packagecom.thealgorithms.datastructures.stacks;
2+
importjava.util.Arrays;
3+
importjava.util.Stack;
4+
/*
5+
Given an array "input" you need to print the first grater element for each element.
6+
For a given element x of an array, the Next Grater element of that element is the
7+
first grater element to the right side of it. If no such element is present print -1.
8+
9+
Example
10+
input = { 2, 7, 3, 5, 4, 6, 8 };
11+
At i = 0
12+
Next Grater element between (1 to n) is 7
13+
At i = 1
14+
Next Grater element between (2 to n) is 8
15+
At i = 2
16+
Next Grater element between (3 to n) is 5
17+
At i = 3
18+
Next Grater element between (4 to n) is 6
19+
At i = 4
20+
Next Grater element between (5 to n) is 6
21+
At i = 5
22+
Next Grater element between (6 to n) is 8
23+
At i = 6
24+
Next Grater element between (6 to n) is -1
25+
26+
result : [7, 8, 5, 6, 6, 8, -1]
27+
28+
1. If the stack is empty Push an element in the stack.
29+
2. If the stack is not empty:
30+
a. compare the top element of the stack with next.
31+
b. If next is greater than the top element, Pop element from the stack.
32+
next is the next greater element for the popped element.
33+
c. Keep popping from the stack while the popped element is smaller
34+
than next. next becomes the next greater element for all such
35+
popped elements.
36+
d. Finally, push the next in the stack.
37+
38+
3. If elements are left in stack after completing while loop then their Next Grater element is -1.
39+
*/
40+
41+
42+
publicclassNextGraterElement {
43+
44+
publicstaticint[]findNextGreaterElements(int[]array) {
45+
46+
if (array ==null) {
47+
returnarray;
48+
}
49+
50+
int[]result =newint[array.length];
51+
Stack<Integer>stack =newStack<>();
52+
53+
for (inti =0;i <array.length;i++) {
54+
while (!stack.isEmpty() &&array[stack.peek()] <array[i]) {
55+
result[stack.pop()] =array[i];
56+
}
57+
stack.push(i);
58+
}
59+
60+
returnresult;
61+
}
62+
63+
publicstaticvoidmain(String[]args)
64+
{
65+
int[]input = {2,7,3,5,4,6,8 };
66+
int[]result =findNextGreaterElements(input);
67+
System.out.println(Arrays.toString(result));
68+
}
69+
}
Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
packagecom.thealgorithms.datastructures.stacks;
2+
importjava.util.Arrays;
3+
importjava.util.Stack;
4+
5+
6+
/*
7+
Given an array "input" you need to print the first smaller element for each element to the left side of an array.
8+
For a given element x of an array, the Next Smaller element of that element is the
9+
first smaller element to the left side of it. If no such element is present print -1.
10+
11+
Example
12+
input = { 2, 7, 3, 5, 4, 6, 8 };
13+
At i = 0
14+
No elements to left of it : -1
15+
At i = 1
16+
Next smaller element between (0 , 0) is 2
17+
At i = 2
18+
Next smaller element between (0 , 1) is 2
19+
At i = 3
20+
Next smaller element between (0 , 2) is 3
21+
At i = 4
22+
Next smaller element between (0 , 3) is 4
23+
At i = 5
24+
Next smaller element between (0 , 4) is 3
25+
At i = 6
26+
Next smaller element between (0 , 5) is 6
27+
28+
result : [-1, 2, 2, 3, 3, 4, 6]
29+
30+
1) Create a new empty stack st
31+
32+
2) Iterate over array "input" , where "i" goes from 0 to input.length -1.
33+
a) We are looking for value just smaller than `input[i]`. So keep popping from "stack"
34+
till elements in "stack.peek() >= input[i]" or stack becomes empty.
35+
b) If the stack is non-empty, then the top element is our previous element. Else the previous element does not exist.
36+
c) push input[i] in stack.
37+
3) If elements are left then their answer is -1
38+
*/
39+
40+
publicclassNextSmallerElement {
41+
publicstaticint[]findNextSmallerElements(int[]array)
42+
{
43+
// base case
44+
if (array ==null) {
45+
returnarray;
46+
}
47+
Stack<Integer>stack =newStack<>();
48+
int[]result =newint[array.length];
49+
Arrays.fill(result, -1);
50+
51+
for (inti =0;i <array.length;i++) {
52+
while (!stack.empty() &&stack.peek() >=array[i])stack.pop();
53+
if (stack.empty()) {
54+
result[i] = -1;
55+
}else {
56+
result[i] =stack.peek();
57+
}
58+
stack.push(array[i]);
59+
}
60+
returnresult;
61+
}
62+
63+
publicstaticvoidmain(String[]args)
64+
{
65+
int[]input = {2,7,3,5,4,6,8 };
66+
int[]result =findNextSmallerElements(input);
67+
System.out.println(Arrays.toString(result));
68+
}
69+
}

0 commit comments

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