力扣-单调栈-503-下一个更大的元素
目录
力扣-单调栈-503 下一个更大的元素Ⅱ
思路和时间复杂度
- 思路：可以首尾重复当作一个长的数组，这样再找右边第一个最大的元素即可，想到了取余的方法，但是还是想的不够，多余了复制数组的操作
- 时间复杂度：
代码
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> res(nums.size(), -1);
stack<int> st;
vector<int> newNums(nums.size() * 2, 0);
for(int i = 0; i < nums.size() * 2; i++){
newNums[i] = nums[i%nums.size()];
}
st.push(0);
for(int i = 1; i <newNums.size(); i++){
if(newNums[i] > newNums[st.top()]){
while(!st.empty() && newNums[i] > newNums[st.top()]){
res[st.top()] = newNums[i];
st.pop();
}
st.push(i % nums.size());
}else{
st.push(i % nums.size());
}
}
return res;
}
};