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] << " "; } }