算法日记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;
}