当前位置: 首页> 科技> 互联网 > 营销推广信息_厦门seo网站优化_网络事件营销_网页设计作品集

营销推广信息_厦门seo网站优化_网络事件营销_网页设计作品集

时间:2025/7/11 1:08:06来源:https://blog.csdn.net/2403_88700185/article/details/145642447 浏览次数:0次
营销推广信息_厦门seo网站优化_网络事件营销_网页设计作品集

一.单调栈

定义:

单调栈是一种特殊的数据结构,本质上是栈,不过在栈的基础上,要求栈内元素保持单调性(单调递增或单调递减)

原理

单调栈在入栈操作时,会根据栈内元素的单调性要求对入栈元素进行处理。当新元素入栈时,如果加入该元素会破坏栈的单调性,就先将栈顶元素出栈,直到加入新元素后栈依然满足单调性,再将新元素入栈。

单调递增栈

栈内元素从栈底到栈顶是单调递增的。当有新元素入栈时,如果新元素小于栈顶元素,则将栈顶元素出栈,直到新元素大于等于栈顶元素,再将新元素入栈。

单调递减栈

栈内元素从栈底到栈顶是单调递减的。当有新元素入栈时,如果新元素大于栈顶元素,则将栈顶元素出栈,直到新元素小于等于栈顶元素,再将新元素入栈。

 

应用场景:

1. 求下一个更大元素

给定一个数组,对于每个元素,找到它右边第一个比它大的元素。

2. 求每日温度问题

给定一个数组表示每天的温度,对于每一天,计算需要等待多少天才能等到一个更暖和的温度。

3. 求柱状图中最大矩形面积

在一个由柱子组成的柱状图中,计算能够形成的最大矩形面积。

 

 这是单调栈的一道非常非常基础的母题,解决这内题我们最先想到的肯定是暴力解法,但实践过后发现时间复杂度太高了直接就T掉了。那么我们必须进行优化,这就要用到单调栈来降低时间复杂度了。由于每个元素最多入栈和出栈一次,因此时间复杂度为O(n),n是数组的长度。代码如下:

//暴力解法
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include<cmath>
#include<stdio.h>using namespace std;void f(vector<int>& a,int n)
{for (int i = 1; i <= n; i++){int b = a[i];int t = 1;int s;for (int j = i + 1; j <= n; j++){if (a[j] > b){t = 0;s = j;break;}}if (t == 0){printf("%d ", s);}else{printf("0 ");}}printf("\n");
}int main()
{int n;cin >> n;vector <int> a(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];}f(a, n);return 0;
}
//单调栈解法
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include<cmath>
#include<stdio.h>using namespace std;
#define max 3000005
void f(vector<int> &a, int n)
{vector<int> ret(n + 1, 0);vector<int> stack(n + 1);int top = -1;for (int i = 1; i <= n; i++){while (top != -1 && a[i] > a[stack[top]]){ret[stack[top]] = i;top--;}top++;stack[top] = i;}for (int i = 1; i <= n; i++){printf("%d ", ret[i]);}cout << endl;
}int main()
{int n;cin >> n;vector<int>a(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];}f(a, n);return 0;
}

二.单调队列

定义:

单调队列本质上是一个队列,不过队列中的元素保持单调递增或单调递减的顺序。与单调栈不同的是,单调队列可以在队首和队尾进行操作,这使得它能够处理滑动窗口这类需要动态维护区间信息的问题。

原理

单调队列的核心原理是在元素入队和出队的过程中,通过一定的规则保证队列中元素的单调性。当有新元素加入队列时,会从队尾开始移除那些破坏单调性的元素,然后将新元素插入到合适的位置,以维持队列的单调性。同时,根据滑动窗口的移动,会从队首移除那些已经不在当前窗口范围内的元素。

操作

入队操作

当有新元素要加入单调队列时,从队尾开始检查,如果队尾元素不满足单调性要求(对于单调递增队列,队尾元素大于新元素;对于单调递减队列,队尾元素小于新元素),则将队尾元素出队,直到满足单调性要求后,将新元素加入队尾。

出队操作

根据滑动窗口的移动,当队首元素不在当前窗口范围内时,将队首元素出队。

应用场景

1. 滑动窗口最大值问题

给定一个数组和一个固定大小的滑动窗口,要求在滑动窗口从数组的一端移动到另一端的过程中,找出每个窗口内的最大值。

2. 优化动态规划问题

在一些动态规划问题中,需要在一个区间内寻找最值来更新状态,使用单调队列可以将时间复杂度从 O(n^2) 优化到 O(n)。

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include<cmath>
#include<algorithm>using namespace std;int n, k;
int a[1000005],e1[1000005],e2[1000005];void min()
{int head = 1, tail = 0;for(int i=1;i<=n;i++){while (head <= tail && e1[head] < i - k + 1) head++;while (head <= tail && a[i] < a[e1[tail]]) tail--;e1[++tail] = i;if (i >= k){cout << a[e1[head]]<<' ';}}cout << endl;
}void max()
{int head = 1, tail = 0;for (int i = 1; i <= n; i++){while (head <= tail && e2[head] < i - k + 1) head++;while (head <= tail && a[i] > a[e2[tail]]) tail--;e2[++tail] = i;if (i >= k){cout << a[e2[head]]<<' ';}}cout << endl;
}
int main()
{cin >> n >> k;for (int i = 1; i <= n; i++){cin >> a[i];}min();max();return 0;
}

关键字:营销推广信息_厦门seo网站优化_网络事件营销_网页设计作品集

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: