常见的网站推广方法,孟州网站建设,房产网站内容建设规划,建站语言有哪些一、题目 二、解题思路#xff1a;
题意为让我们找到每个元素的左边第一个比它小的元素#xff0c;若不存在则输出-1
2.1法一#xff1a;暴力#xff08;0n2#xff09;
首先#xff0c;我们可以想到最朴素的算法#xff1a;直接暴力两层for达成目标核心代码如下
题意为让我们找到每个元素的左边第一个比它小的元素若不存在则输出-1
2.1法一暴力0n2
首先我们可以想到最朴素的算法直接暴力两层for达成目标核心代码如下 int n;cinn;for(int i1;in;i){cina[i];}memset(l,-1,sizeof l);for(int i1;in;i) //遍历{for(int ji-1;j1;j--) //从i开始往左找目标值{if(a[j]a[i]) //表示找到了{l[i]a[j];break;}}}for(int i1;in;i) coutl[i] ;也就是对于每一个元素都往前去找对应的元素
2.2单调栈
核心思路为利用栈的特性来维护一个单调不减栈 1、假设此时栈里有这些元素此时有又来了一个元素mid 如果(mid)st.top()则表明此时的mid一定的更优的也就意味着此时st.top()它一定不可能成为答案因此我们可以把它删掉st.pop() *也就是说只要一个元素是小于栈顶元素的那么它的左边元素就全部作废不会对结果产生印象一个while即可 2、因此我们可以来模拟单调栈的过程 1):此时栈为空所以7---1并且让7进栈 *2):此时8mid想进来可以发现st.top()mid因此st.top一定就是8左边离它最近且比它小的元素。接着让8入栈 3):接下来轮到5(mid)可以发现此时midst.top()因此应该对st进行修改让midst.top()。可以用while来实现一直让st.pop()直到midst.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];stackintst; //存储序列下标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;
}
