首页 🍒LeetCode,🐶算法

题目

PpC8YRpizs.png

思路

暴力法遍历寻找所有元素的下一个更大元素,C++过了。

单调栈:
暴力法如果遇到一串单调递减的字符串会所有元素都计算一遍浪费时间,将这些元素放入一个栈中,如果遇到了比栈顶元素大的元素k,那么栈顶元素的下一个更大元素就是k,然后把栈顶pop出去,然后k逐一与栈顶比较直到遇到比k大的将k加入栈中。

遍历时:
如果栈为空则push。
不空则与top进行比较:

比top大则栈进行pop,继续与pop比较,直到比top小或栈空。
比top小则入栈。

栈中应该存储数组坐标以便进行比较。
因为是环形数组,所以会遍历两遍数组,坐标可以用i % nums.size()表示。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> res(nums.size(), -1);
        stack<int> st;
        for (int i = 0; i < 2 * nums.size(); i++) {
            while (!st.empty() && nums[st.top()] < nums[i % nums.size()]) {
                res[st.top()] = nums[i % nums.size()];
                st.pop();
            }
            st.push(i % nums.size());
        }
        return res;
    }
};



文章评论