广元企业网站建设,设计图片的app软件,网络营销方案毕业设计,天津网站建站模板思路#xff1a;
与之前 739、1475 单调栈的问题如出一辙#xff0c;唯一不同的地方就是对于遍历完之后。栈中元素的处理#xff0c;之前的栈中元素因无法找到符合条件的值#xff0c;直接加入vector中。而这里需要再重头遍历一下数组#xff0c;找是否有符合条件的…
思路
与之前 739、1475 单调栈的问题如出一辙唯一不同的地方就是对于遍历完之后。栈中元素的处理之前的栈中元素因无法找到符合条件的值直接加入vector中。而这里需要再重头遍历一下数组找是否有符合条件的如果仍然找不到的话才会把它赋值然后加入vector中。
代码
class Solution {
public:vectorint nextGreaterElements(vectorint nums) {int n nums.size();vectorint ans(n);stackint st;for (int i 0; i n; i) {int t nums[i];// 出栈并计算while (!st.empty() t nums[st.top()]) {int x st.top();ans[x] t;st.pop();}// 入栈while (st.empty() || (t nums[st.top()] i ! st.top())) {st.push(i);}}// 处理遍历完之后栈中剩余的元素。while (!st.empty()) {int x st.top();// 从头遍历数组看是否有符合要求的值。int i 0;for (i 0; i n; i) {if (nums[i] nums[x]) {ans[x] nums[i];break;}}if (i n) ans[x] -1;st.pop();}return ans;}
};
注意点
for循环中的入栈出栈顺序非常重要
出栈放在最后则新元素无法入栈。
运行结果
