做游戏难吗比做网站,wordpress百度地图,基于jsp的购物网站开发,所有网站都要备案吗详细解读 至此我们可以解答最开始的疑问#xff0c;单调栈的根本作用在于求得「每一个数字在原始序列中左 / 右边第一个大于 / 小于它自身的数字」#xff0c;并且由于每一个数字只会入栈一次且最多出栈一次#xff0c;因此总的时间复杂度为 O ( n ) 。
另外需要注意#… 详细解读 至此我们可以解答最开始的疑问单调栈的根本作用在于求得「每一个数字在原始序列中左 / 右边第一个大于 / 小于它自身的数字」并且由于每一个数字只会入栈一次且最多出栈一次因此总的时间复杂度为 O ( n ) 。
另外需要注意一次「单调递增栈」的过程可以求得每个数字左边第一个小于等于它的数以及右边第一个小于它的数此处需注意「小于等于」和「小于」的区别。除此之外「单调递减栈」将上述的「小于」改为「大于」即可成立。 ————————————————
int tt 0;
for (int i 1; i n; i )
{while (tt check(q[tt], i)) tt -- ;stk[ tt] i;
}
下一个更大元素 I
class Solution {
public:
vectorint nextGreaterElement(vectorint nums1, vectorint nums2) {//首先构建一个单调栈 stackintstk;//使用vector来纪录当前对应各个元素下一个更大值的情况vectorintq(nums2.size());//根据题意需要寻找右侧第一个目标值所以从vector最后一个元素处理for (int i nums2.size() - 1; i 0; i--) {int x nums2[i];//根据题意可设置为单调递减栈即从栈底到栈顶为降序while (stk.size() x stk.top()) stk.pop();//如果单调栈为空说明不存在符合条件的元素返回-1if (stk.empty()) q[i] -1;//当前栈顶元素为右侧第一个比当前x大的元素并且记录在当前下标对应位置else q[i] stk.top();//将当前元素入栈stk.push(x);}unordered_mapint, int hash;for (int i 0; i nums2.size(); i)hash[nums2[i]] i;vectorint res;for (auto x : nums1)res.push_back(q[hash[x]]);return res;}
};
