單調棧
給定一個長度為N的整數數列，輸出每個數左邊第一個比它小的數，如果不存在則輸出-1。

暴力做法是兩重循環

for(int i=0;i<n;i++)for(int j=i-1;j>=0;j--)if(a[i]>a[j]) break; cout<<a[j]<<endl;

單調棧寫法
單調棧：找到比目標小的且距離最近的數在什么位置。
如果左邊的數大，就會丟棄。
此處是使用數組模擬棧。
復雜度O(n)

#include<iostream> #include<algorithm> using namespace std; const int maxn=1e5+10; int stk[maxn],tt;//全局變量，初始化為0 //stk棧數組，tt棧頂 int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++){int x;scanf("%d",&x);while(tt&&stk[tt]>=x) tt--;//棧不空而且棧頂元素大于x，該元素彈棧if(tt) printf("%d ",stk[tt]);else printf("-1 ");stk[++tt]=x;//x放入棧}return 0; } 《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的单调栈板子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。