算法日记8：StarryCoding60（单调栈）

一、题目

二、解题思路：

• 题意为让我们找到每个元素的左边第一个比它小的元素，若不存在则输出-1

2.1法一：暴力（0n²）

• 首先，我们可以想到最朴素的算法：直接暴力两层for达成目标
• 核心代码如下：

   int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}memset(l,-1,sizeof l);for(int i=1;i<=n;i++)    //遍历{for(int j=i-1;j>=1;j--)    //从i开始往左找目标值，{if(a[j]<a[i]) //表示找到了{l[i]=a[j];break;}}}for(int i=1;i<=n;i++) cout<<l[i]<<' ';

也就是对于每一个元素，都往前去找对应的元素

2.2：单调栈

• 核心思路为利用栈的特性来维护一个单调不减栈
  

• 1、假设，此时栈里有这些元素，此时，有又来了一个元素（mid）

• 如果(mid)<st.top()则表明此时的mid一定的更优的，也就意味着此时st.top()它一定不可能成为答案，因此我们可以把它删掉st.pop()
  
  *也就是说只要一个元素是小于栈顶元素的，那么它的左边元素就全部作废（不会对结果产生印象），一个while即可
  

• 2、因此我们可以来模拟单调栈的过程

• 1):此时栈为空，所以7-->-1，并且让7进栈
  
  *2):此时，8（mid）想进来，可以发现st.top()<mid，因此，st.top一定就是8左边离它最近且比它小的元素。接着让8入栈
  
• 3):接下来轮到5(mid)，可以发现此时mid<st.top()，因此，应该对st进行修改，让mid>st.top()。可以用while来实现，一直让st.pop()直到mid>st.top()，接着让mid入栈

因此可以总结出我们的规则

三、完整代码如下：

PS:也可以使用数组来模拟栈的过程

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int N = 2e5 + 7; // 定义最大范围
int a[N],l[N];void solve()
{memset(l,-1,sizeof l);int n; cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];stack<int>st;   //存储序列下标for (int i = 1; i <= n; i++){while (!st.empty() && a[st.top()] >= a[i]) //非空 且 栈顶元素>=a[i]{st.pop();//出栈}if (st.empty()){l[i] = -1;  //此时栈为空，则表示没有比a[i]更小的数    }else if (a[st.top()] < a[i])     //否则此时栈顶元素就是距离a[i]最近的小于元素{l[i] = a[st.top()]; //那么此时栈顶元素即是符合条件的 }st.push(i); //入栈}for (int i = 1; i <= n; i++) cout << l[i] << ' ';
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ = 1; //cin >> _;while (_--) solve();system("pause");return 0;
}