一个常用的数据结构维护套路

经常有这样的问题，需要维护序列中每个元素向左(右)第一个(最后一个)大于(小于)它的值。
对此，我们完全可以使用线段树等高级数据结构或者使用二分查找等方式得到一个时间复杂度为nlogn的解决方案。但对于该问题这样做就显得有点杀鸡用牛刀了。实际上我们可以用更加简洁的代码得到一种线性的解决方案。

问题1：求每个元素向左第一个大于它的值
解决方案：使用栈维护
相关代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> a(n + 1), l(n + 1, 0);
  // l[i]表示第i个元素左边第一个比它大的元素下标 若不存在为0 
  stack<int> st;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    while (!st.empty() && a[st.top()] <= a[i]) st.pop();
    if (!st.empty()) l[i] = st.top();
    st.push(i);
  }
  for (int i = 1; i <= n; i++)
    cout << l[i] << ' ';
  return 0;
} 

问题2：求每个元素向左最后一个大于它的值
解决方案：按元素值从大到小遍历数组中的元素下标，维护最小下标。复杂度为O(nlogn)或O(n+c)(使用桶)
相关代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> a(n + 1), l(n + 1, 0);
  // l[i]表示第i个元素左边最后一个比它大的元素下标 若不存在为0 
  vector<int> nums;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    nums.push_back(a[i]);
  }
  sort(nums.begin(),nums.end());
  nums.erase(unique(nums.begin(),nums.end()),nums.end());
  int m = (int)nums.size();
  vector<vector<int> > pos(m + 1, vector<int>());
  for (int i = 1; i <= n; i++) {
    int x = lower_bound(nums.begin(),nums.end(),a[i]) - nums.begin() + 1;
    pos[x].push_back(i);
  }
  int minPos = n + 1; 
  for (int i = m; i >= 1; i--) {
    if (!pos[i].empty()) {
      for (int id: pos[i])
        if (id > minPos) l[id] = minPos;
      for (int id: pos[i]) minPos = min(minPos, id);
    }
  }
  for (int i = 1; i <= n; i++)
    cout << l[i] << ' ';
  return 0;
}