9.13百度笔试-算法
一共两道编程题，比较简单，AK了，记录一下第二题的思路：
题目：给定一个n个数的数组，然后进行m次操作，每一次有两个变量t和k，t=1代表对数组前k个数升序排列，t=2代表对数组前k个数降序排列
思路：
看着比较简单，首先用暴力每一次操作以后都重新排序，只能过81%
后来仔细一想，实际是一个单调栈问题，无论前面操作了多少次，只要有一个更大的k值，前面的排序就是无用的，故只需记录一个递减单调栈即可。
还需要注意的一点是，记录了单调递减的单调栈后，由于要依次由栈底到栈顶做排序，故再新创建一个栈（类似于两个栈实现队列功能），利用两个栈实现最终按k值由大到小每次排序。
附上代码：
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
stack<pair<int, int>> q, q2;
int t, k;
for (int i = 0; i < m; i++) {
cin >> t >> k;
while (!q.empty() && q.top().second < k) {
q.pop();
}
q.push({ t,k });
}
while (!q.empty()) {
q2.push(q.top());
q.pop();
}
while (!q2.empty()) {
auto temp = q2.top();
if (temp.first == 1) {
sort(nums.begin(), nums.begin() + temp.second);
}
else {
sort(nums.begin(), nums.begin() + temp.second, [](int& a, int& b) {
return a > b;
});
}
q2.pop();
}
for (int i = 0; i < n; i++) {
cout << nums[i] << " ";
}
} 
查看7道真题和解析
爱玛科技公司福利 8人发布