# Next Greater Element II - Miscellaneous / Monotonic Stack

I think we can make the java solution bit simpler by not having a inner class

public static List nextGreaterElements(List nums) {
// we will loop the input twice as it is considered as circular
int n = nums.size();
int i = n * 2 - 1;

Integer[] result = new Integer[n];
// intial value -1; if we dont find next greater value then we leave -1 as it is;
Arrays.fill(result, -1);

// maintaining decreasing value only is deque
Deque deque = new ArrayDeque();

while (i >= 0) {
int currIndex = i % n;
while (!deque.isEmpty() && nums.get(currIndex) >= deque.getLast()) {
deque.removeLast();
}
if (!deque.isEmpty())
result[currIndex] = deque.getLast();
iā;
}

return List.of(result);
}

#include // copy
#include // cin, cout
#include // back_inserter, istream_iterator, ostream_iterator, prev
#include // istringstream
#include // getline, string
#include // vector
#include
#include
std::vector next_greater_elements(std::vector t) {
std::vector ans(t.size(), -1);

``````std::stack<std::pair<int, int>> st;

for(int i = 0; i < t.size(); i++){
while(!st.empty() && st.top().first < t[i]){

ans[st.top().second]  = t[i];
st.pop();
}

st.push({t[i], i});
}

for(int i = 0; i < t.size(); i++){
while(!st.empty() && st.top().first < t[i]){

ans[st.top().second]  = t[i];
st.pop();
}

st.push({t[i], i});
}

return ans;
``````

}

template
std::vector get_words() {
std::string line;
std::getline(std::cin, line);
std::istringstream ss{line};
std::vector v;
std::copy(std::istream_iterator{ss}, std::istream_iterator{}, std::back_inserter(v));
return v;
}

template
void put_words(const std::vector& v) {
if (!v.empty()) {
std::copy(v.begin(), std::prev(v.end()), std::ostream_iterator{std::cout, " "});
std::cout << v.back();
}
std::cout << ā\nā;
}

int main() {
std::vector nums = get_words();
std::vector res = next_greater_elements(nums);
put_words(res);
}

Simpler java solution

private static class Element {
private int val;
private int index;

``````    public Element(int val, int index) {
this.val = val;
this.index = index;
}
public Element(Element other) {
this.val = other.val;
this.index = other.index;
}
}

public static List<Integer> nextGreaterElements(List<Integer> nums) {
List<Element> elements = new ArrayList<>();
List<Integer> result = new ArrayList<>();

// set the default
for(int i = 0; i < nums.size(); i++)

for(int i = 0; i < nums.size(); i++)

// repeat elements
for(int i = 0; i < nums.size(); i++)

Stack<Element> stack = new Stack<>();

for(Element e: elements)
{
if (stack.isEmpty() || e.val <= stack.peek().val)
stack.push(e);
else {
while(!stack.isEmpty() &&  e.val > stack.peek().val)
{
Element elmt = stack.pop();
result.set(elmt.index, e.val);

}
stack.push(e);
}
}

return result;
}
``````