1、首先想用一个常规解法，是n^2复杂度，果然只能过50
#include<iostream>
#include<vector>
#include<stack>
using namespace std;void treatM(vector<int>& m, vector<int>& res, int n){for(int i = 0; i < n; i++){stack<int> leftS;int left = 0;for(int j = i-1; j >= 0; j--){if(leftS.empty()||m[j]>=leftS.top()){left++;leftS.push(m[j]);}}stack<int> rightS;int right = 0;for(int j = i+1; j < n; j++){if(rightS.empty()||m[j]>=rightS.top()){right++;rightS.push(m[j]);}}res[i] = left+right+1;}
}int main(){int n;cin >> n;vector<int> m(n,0);for(int i = 0; i < n; i++){cin >> m[i];}vector<int> res(n,0);treatM(m,res,n);for(int i = 0; i < n; i++){cout << res[i] << ' ';}return 0;
}
2、尝试用单调栈来解决：这里是评论区大佬的代码 ，tql
- 这里并不是以某个位置为分界点，而是分别从两侧来向另一侧遍历
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
vector<int> a, b;
stack<int> st1, st2;int main() {int n, x[100001];cin >> n;int ans = 0;for (int i = 0; i < n; i++) cin >> x[i];for (int i = 0, j = n - 1; i < n, j >= 0; i++, j--) {a.push_back(st1.size());b.push_back(st2.size());while (!st1.empty() && st1.top() <= x[i]) st1.pop();while (!st2.empty() && st2.top() <= x[j]) st2.pop();st1.push(x[i]);st2.push(x[j]);}reverse(b.begin(), b.end());for (int i = 0; i < n; i++) cout << b[i] + a[i] + 1<< " ";return 0;
}