Next Greater Element II - Miscellaneous / Monotonic Stack

Problems
1

https://algo.monster/problems/next_greater_element_ii

2

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();
deque.addLast(nums.get(currIndex));
i–;
}

return List.of(result);
}

3

#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);
}

4

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++)
        result.add(-1);
    
    // add elements
    for(int i = 0; i < nums.size(); i++)
        elements.add(new Element(nums.get(i), i));
    
    // repeat elements
    for(int i = 0; i < nums.size(); i++)
        elements.add(new Element(elements.get(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;
}
5

We can combine two loops to make it clean

def next_greater_elements(nums: List[int]) -> List[int]:
    res = [-1] * len(nums)
    stack = []
    for i in range(len(nums) * 2):
        i = i % len(nums)
        while stack and nums[i] > nums[stack[-1]]:
            j = stack.pop()
            res[j] = nums[i]
        if res[i] == -1:
            stack.append(i)
    return res