当前位置：首页 > news >正文

网站规划的基本步骤/上热门最火标题

news 2025/7/5 10:49:30

网站规划的基本步骤,上热门最火标题,网站开发个性化,昆山做网站的公昆山做网站的公司司1.单调栈的模版 4种情况代码实现： //1.找数字左侧比它大并且是最近的数的下标 //单调栈：单调递减，如果比它小，不要，比它大，推入队列 #include<iostream> #include<stack> #include<vect…

1.单调栈的模版

4种情况

代码实现：

//1.找数字左侧比它大并且是最近的数的下标
//单调栈：单调递减，如果比它小，不要，比它大，推入队列
#include<iostream>
#include<stack>
#include<vector>
using namespace std;const int N = 1e3 + 10;
int n;
int a[N];
int ret[N];
//1.找左侧最近的且比它大的数字
void fun1()
{stack<int> s;for (int i = 1; i <= n; i++){int t = a[i];while (s.size() && a[s.top()] <= t)s.pop();if (s.size())ret[i] = s.top();s.push(i);}for (int i = 1; i <= n; i++){cout << ret[i] << " ";}
}
//2.找左侧最近且比它小的数字
void fun2()
{stack<int> s;for (int i = 1; i <= n; i++){int t = a[i];while (s.size() && a[s.top()] >= t)s.pop();if (s.size())ret[i] = s.top();s.push(i);}for (int i = 1; i <= n; i++){cout << ret[i] << " ";}
}
//3.找右侧最近且比它大的元素，1的逆序
void fun3()
{stack<int> s;for (int i = n; i >= 1; i--){int t = a[i];while (s.size() && a[s.top()] >= t)s.pop();if (s.size())ret[i] = s.top();s.push(i);}for (int i = 1; i <= n; i++){cout << ret[i] << " ";}
}
//4.找右侧最近且比它小的元素，2的逆序
void fun2()
{stack<int> s;for (int i = n; i >= 1; i--){int t = a[i];while (s.size() && a[s.top()] >= t)s.pop();if (s.size())ret[i] = s.top();s.push(i);}for (int i = 1; i <= n; i++){cout << ret[i] << " ";}
}
int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];fun2();}

注意：

栈里面存的是元素的下标。

总结和巧记：

1.记录详情 - 洛谷 | 计算机科学教育新生态

#include<iostream>
#include<stack>
using namespace std;int n;
const int N = 3e6+10;
int a[N];
int ret[N];int main()
{cin>>n;for(int i = 1;i <= n;i++)cin>>a[i];stack<int> s;for(int i = n;i >= 1;i--){int t = a[i];while(s.size()&&a[s.top()]<=t)s.pop();if(s.size())ret[i] = s.top();s.push(i);}for(int i = 1;i <= n;i++)cout<<ret[i]<<" ";
}

2.P1901 发射站 - 洛谷

#include<iostream>
#include<stack>
using namespace std;const int N = 1e6 + 10;
int h[N], v[N];
int ret[N];int main()
{int n; cin >> n;for (int i = 1; i <= n; i++){cin >> h[i] >> v[i];}stack<int> s;//找左边最近且比它大的元素for (int i = 1; i <= n; i++){int t = h[i];//当前元素while (s.size() && h[s.top()] <= t)//在栈中找到一个比它大的元素{s.pop();}if (s.size())ret[s.top()] += v[i];//比它大的元素加上它的powers.push(i);//把该元素推进栈中}//清空栈while (s.size())s.pop();//找右边最近且比它大的元素for (int i = n; i >=1; i--){int t = h[i];while (s.size() && h[s.top()] <= t){s.pop();}if (s.size())ret[s.top()] += v[i];//比它大的元素加上它的powers.push(i);}int res = 0;for (int i = 1; i <= n; i++){res = max(res, ret[i]);}cout << res << endl;
}

前后使用单调栈，找出左右离他最近并且比它的元素，把它的power加到该元素下，再把下标推入栈中

3.SP1805 HISTOGRA - Largest Rectangle in a Histogram - 洛谷

#include<iostream>
#include<stack>
using namespace std;typedef long long LL;
const int N = 1e5 + 10;
LL a[N];
LL l[N];//记录每个元素左侧比它小的元素的下标
LL r[N];//记录每个元素右侧比它小的元素的下标
int n;int main()
{while (cin >> n, n){for (int i = 1; i <= n; i++)cin >> a[i];stack<int> s;//找每个元素左边比它小的元素的下标for (int i = 1; i <= n; i++){int t = a[i];while (s.size() && a[s.top()] >= t){s.pop();}if (s.size())l[i] = s.top();else l[i] = 0;//找不到的话，栈就变成空了，就把左侧设置成0s.push(i);}//清空栈while (s.size())s.pop();//找每个元素右侧比它小的元素的下标for (int i = n; i >= 1; i--){int t = a[i];while (s.size() && a[s.top()] >= t)s.pop();if (s.size())r[i] = s.top();else r[i] = n + 1;//找不到的话，栈就变成空了，就把左侧设置成n+1s.push(i);}LL ret = 0;for (int i = 1; i <= n; i++){ret = max(ret, a[i] * (r[i] - l[i] - 1));}cout << ret << endl;}
}