单调栈NGN
2021-03-07 本文已影响0人
Talk1sCheap
image.png单调栈除了用来解决下个更大的问题外,几乎没有其他用途
- 从后往前看
- 这里的单调栈并不是严格意义的单调栈,而是不断与栈顶元素比较
每个元素都会进栈,具体则是和栈顶比,
for(int i=nums1.length-1;i>=0;i--){
while(!s.isEmpty()&&nums1[i]>=s.peek()){
s.pop();
}
int v=s.isEmpty()?-1:s.peek();
s.push(nums1[i]);
if(i<n){
res[i]=v;
}
}
循环
n的可以用2n来表示 这样子就会方便很多