单调栈NGN

2021-03-07  本文已影响0人  Talk1sCheap

单调栈除了用来解决下个更大的问题外,几乎没有其他用途

image.png
  1. 从后往前看
  2. 这里的单调栈并不是严格意义的单调栈,而是不断与栈顶元素比较
    每个元素都会进栈,具体则是和栈顶比,
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来表示 这样子就会方便很多

上一篇下一篇

猜你喜欢

热点阅读