solution.h

JadonChan

Mar 21st, 2025

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 1.11 KB | None | 0 0

raw download clone embed print report

//
// Created by Jadon Chan on 2025/3/21.
//
#ifndef MINIMAL_LARGER_SUFFIX_SOLUTION_H
#define MINIMAL_LARGER_SUFFIX_SOLUTION_H
#include <vector>
#include <stack>
class solution {
public:
std::vector<int> minimal_larger_suffix(std::vector<int> vec) {
std::stack<int> stk;
int n = static_cast<int>(vec.size());
int index_of_top = n;
std::vector<int> ret(n);
for (auto i = n - 1; i >= 0; i--) {
int ans;
if (stk.empty()) { // Initial state
ans = -1;
}
// If top element is less than or equal to elem i,
// there's no element larger than elem i between elem i and elem index_of_top.
// Thus, the answer for this position is behind index_of_top. So it's the same as answer for index_of_top
else if (stk.top() <= vec[i]) {
ans = ret[index_of_top];
}
// If top element is greater than elem i,
// the answer is the last popped element
while(!stk.empty() && stk.top() > vec[i]) {
ans = stk.top();
stk.pop();
}
ret[i] = ans;
stk.push(vec[i]);
index_of_top = i;
}
return ret;
}
};
#endif //MINIMAL_LARGER_SUFFIX_SOLUTION_H

Add Comment

Please, Sign In to add comment