#include<bits/stdc++.h>
using namespace std;

struct Student
{
    int id;
    int score;
};

bool cmp(Student a, Student b)
{
    if(a.score == b.score) return a.id < b.id;
    return a.score < b.score;
}

int main()
{
    int n;
    cin >> n;
    Student stu[n];
    for(int i = 0; i < n; i ++ )
    {
        cin >> stu[i].id >> stu[i].score;
    }

    sort(stu, stu + n, cmp);
    for(int i = 0; i < n; i ++ )
    {
        cout << stu[i].id <<" "<<stu[i].score << endl;
    }
    return 0;
}

稳定排序：相同元素相对位置不发生变化（归并排序）
不稳定：快排，堆排。sort排序

#include<bits/stdc++.h>
using namespace std;

struct Student
{
    char nam[10];
    int score;
    int id;
};

bool cmp1(Student a, Student b)
{
    if(a.score == b.score) return a.id < b.id;
    return a.score > b.score;
}

bool cmp2(Student a, Student b)
{
    if(a.score == b.score) return a.id < b.id;
    return a.score < b.score;
}
int main()
{
    int n, f;
    cin >> n >> f;
    Student stu[n];
    for(int i = 0; i < n; i ++ )
    {
        cin >> stu[i].nam >> stu[i].score;
        stu[i].id = i;
    }

    if(f == 0) sort(stu, stu + n, cmp1);
    else sort(stu, stu + n, cmp2);
    for(int i = 0; i < n; i ++ )
    {
        cout << stu[i].nam <<" "<<stu[i].score << endl;
    }
    return 0;
}

Sort

• sort()函数可以接受两个或三个参数，第一个参数是要排序的数组的起始地址，第二个参数是结束的地址（最后一位要排序的地址的下一地址），第三个参数是排序的方法（一般为一个函数），可以指定升序或降序，如果不写第三个参数，默认为升序。
• 使用greater < data_type >()作为第三个参数，例如：sort(a,a+n,greater< int >())。或者自定义一个比较函数cmp()，返回值是bool型，规定了什么样的关系才是“大于”，例如：bool cmp(int x,int y) { return x > y; }，然后作为第三个参数传入sort()函数，例如：sort(a,a+n,cmp)。
• 如果要对自定义类型（如结构体）进行排序，需要定义一个比较函数cmp()，返回值是bool型，规定了什么样的关系才是“小于”。比较函数可以根据结构体中的某个或多个成员变量来进行比较。

例如，如果有一个结构体student，包含grade, name, age三个成员变量，想要按照grade升序，name升序，age升序的顺序对一个student类型的数组stu[]进行排序，可以写出如下代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;

struct student {
  int grade;
  char name[101];
  int age;
}stu[1001];

bool cmp(student a,student b)//定义比较规则
{
  int temp = strcmp(a.name,b.name);
  if(a.grade!=b.grade) return a.grade<b.grade; //升序
  else if(temp != 0)//升序 ，要做是否相等的判断
    return temp<0;
  else return a.age < b.age;//升序
}

int main()
{
  int n;
  while(scanf("%d",&n)!=EOF)
  {
    for(int i=0;i<n;i++)
      scanf("%s%d%d",&stu[i].name , &stu[i].age,&stu[i].grade);
    sort(stu,stu+n,cmp);//对结构体排序
    for(int i=0;i<n;i++)
      printf("%s %d %d\n",stu[i].name , stu[i].age,stu[i].grade);
  }
  return 0;
}

• calc函数的作用是计算一个数组中，以每个元素为高度的最大矩形面积，并返回最大值。它利用了单调 栈的思想，可以在 O(n) 的时间复杂度内完成。
• max(D[i+1],calc(s[i],m))这行代码的作用是计算第 i 行及其以下部分的最大子矩阵面积。它先用 calc 函数计算出第 i 行的最大子矩阵面积，然后和第 i+1 行及其以下部分的最大子矩阵面积（已经预处理过）取较大值，作为当前部分的最大值。

#include <iostream>
#include <string.h>
using namespace std;
const int N = 2010;

int n, m;
char g[N][N];
int l[N], r[N], q[N];
int U[N], D[N], L[N], R[N]; // 上下左右各个部分的最大值（上部分为第i行及其以上部分）
int s[N][N];

int calc(int h[], int n)
{

    h[0] = h[n + 1] = -1; // 在数组两端加上哨兵，方便处理边界情况
    int tt = 0;
    // 左边
    q[0] = 0;
    for (int i = 1; i <= n; i++) // 从左往右遍历数组
    {
        while (h[q[tt]] >= h[i])
            // 如果当前元素小于等于栈顶元素，就弹出栈顶元素，直到找到第一个比当前元素小的元素或者栈为空
            tt--;
        l[i] = q[tt];
        q[++tt] = i;
    }
    // 右边
    tt = 0;
    q[0] = n + 1; //
    for (int i = n; i > 0; i--)
    {
        while (h[q[tt]] >= h[i])
            tt--;
        r[i] = q[tt];
        q[++tt] = i;
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, h[i] * (r[i] - l[i] - 1));
    // 遍历所有位置，计算以每个位置为高度的最大矩形面积，并更新最大值
    return res;
}

void init()
{
    // 预处理上半部分
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            if (g[i][j] == '1')
                s[i][j] = s[i - 1][j] + 1;
            // 如果当前位置是 1，就累加上一行的值
            else
                s[i][j] = 0;
        // 在i-1上半部分最大值和新的值之间取最大
        U[i] = max(U[i - 1], calc(s[i], m));
    }
    memset(s, 0, sizeof s);
    // 下半部分
    for (int i = n; i; i--)
    {
        for (int j = 1; j <= m; j++)
            if (g[i][j] == '1')
                s[i][j] = s[i + 1][j] + 1;
            else
                s[i][j] = 0;
        D[i] = max(D[i + 1], calc(s[i], m));
    }
    memset(s, 0, sizeof s);
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
            if (g[j][i] == '1')
                s[i][j] = s[i - 1][j] + 1;
            else
                s[i][j] = 0;
        L[i] = max(L[i - 1], calc(s[i], n));
    }
    memset(s, 0, sizeof s);
    for (int i = m; i; i--)
    {
        for (int j = 1; j <= n; j++)
            if (g[j][i] == '1')
                s[i][j] = s[i + 1][j] + 1;
            else
                s[i][j] = 0;
        R[i] = max(R[i + 1], calc(s[i], n));
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> g[i] + 1;
    init();

    int Q;
    cin >> Q;
    while (Q--)
    {
        int x, y;
        cin >> x >> y;
        x++;
        y++;
        cout << max(max(U[x - 1], D[x + 1]), max(L[y - 1], R[y + 1])) << endl;
        ;
    }
    return 0;
}

1.单调栈结构

给定一个不含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。

输入描述：

第一行输入一个数字 n，表示数组 arr 的长度。
以下一行输出 n个数字，表示数组的值。

输出描述：

输出n行，每行两个数字 L 和 R，如果不存在，则值为-1，下标从0开始。

输入：
7
3 4 1 5 6 2 7

输出：
-1 2
0 2
-1 -1
2 5
3 5
2 -1
5 -1

直接申请a[N], N = 1e6爆内存
找元素i左右最近的较小值，维护单调递增的栈
当栈顶小于当前元素，而次顶元素也比栈顶小，则记录答案
栈顶大于当前元素，直接入栈
最后处理栈内剩余元素

#include<bits/stdc++.h>
using namespace std;
//const int N = 100010;
int n;

int main()
{
    cin >> n;
    vector<int>a(n);
    for(int i = 0; i < n; i ++ )
        cin >> a[i];
    stack<int> stk;
    vector<vector<int>>ans(n, vector<int>(2));
    for(int i = 0; i < n; i ++ )
    {
        while(!stk.empty() && a[stk.top()] > a[i])
        {
            int t = stk.top();
            stk.pop();
            int l = stk.empty() ? -1 : stk.top();//左边比a[t]小的
            //右边就是i
            ans[t][0] = l;
            ans[t][1] = i;
        }
        stk.push(i);
    }

    //单调栈中剩余元素
    while( !stk.empty() )
    {
        int r = -1; //单调栈中递增，右边一定没有比当前小的元素
        int t = stk.top();
        stk.pop();
        int l = stk.empty() ? -1 : stk.top();
        ans[t][0] = l;
        ans[t][1] = r;
    }
    for(int i = 0; i < n; i ++ )
    {
        cout << ans[i][0] <<" "<<ans[i][1] << endl;
    }

    return 0;
}

2.单调栈结构(进阶)

给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。

• 单调栈中每个元素改为链表，链表存相同值

#include <bits/stdc++.h>
using namespace std;
// const int N = 100010;
int n;

int main()
{
    cin >> n;
    vector<int> a(n);
    // for (int i = 0; i < n; i++)
    //     cin >> a[i];
    // stack<int> stk;
    stack<list<int>> stk;
    vector<vector<int>> ans(n, vector<int>(2));
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        while (!stk.empty() && a[stk.top().front()] > a[i])
        {
            // int t = stk.top();
            list<int> t = stk.top();
            stk.pop();
            int l = stk.empty() ? -1 : stk.top().back(); // 左边比a[t]小的
            // 右边就是i
            for (auto x : t) // 遍历链表
            {
                ans[x][0] = l;
                ans[x][1] = i;
            }
        }
        if (!stk.empty() && a[stk.top().front()] == a[i])
        {
            stk.top().push_back(i); // 相等元素加入链表中
        }
        else
            stk.push({i});
    }

    // 单调栈中剩余元素
    while (!stk.empty())
    {
        int r = -1; // 单调栈中递增，右边一定没有比当前小的元素
        list<int> t = stk.top();
        stk.pop();
        int l = stk.empty() ? -1 : stk.top().back();
        for (auto x : t) // 遍历链表
        {
            ans[x][0] = l;
            ans[x][1] = r;
        }
    }
    for (int i = 0; i < n; i++)
    {
        printf("%d %d\n",ans[i][0],ans[i][1]);
    }

    return 0;
}

3.直方图中最大的矩形

直方图是由在公共基线处对齐的一系列矩形组成的多边形。矩形具有相等的宽度，但可以具有不同的高度。例如，图例左侧显示了由高度为 2,1,4,5,1,3,3的矩形组成的直方图，矩形的宽度都为 1
：

通常，直方图用于表示离散分布，例如，文本中字符的频率。现在，请你计算在公共基线处对齐的直方图中最大矩形的面积。图例右图显示了所描绘直方图的最大对齐矩形。

思路

先从考虑枚举，再优化。每个矩阵对应一个高度，宽度向两边延申至高度将要减小为止。因此，找到每个矩阵左右第一个小于当前高度的矩阵，符合单调栈模型

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;

int n;
int h[N], l[N], r[N], q[N];
//h存储矩阵高度，l和r存储左右边界，q单调栈

int main()
{
    while (scanf("%d", &n), n)
    {
        for (int i = 1; i <= n; i++)//下标从1开始
            scanf("%d", &h[i]);
        h[0] = h[n + 1] = -1;
        // 在两端添加哨兵元素，方便处理边界情况
        int tt = 0;//栈顶指针
        q[0] = 0;
        for (int i = 1; i <= n; i++)//每个元素左边第一个比它小的元素
        {
            while (h[i] <= h[q[tt]])
            // 如果当前矩形高度小于等于栈顶元素对应的高度，则弹出栈顶元素
                tt--;
            l[i] = q[tt];
            q[++tt] = i;
        }

        tt = 0;
        q[0] = n + 1;
        for (int i = n; i; i--)// 从右到左遍历每个矩形
        {
            while (h[i] <= h[q[tt]])
                tt--;
            r[i] = q[tt];
            q[++tt] = i;
        }
        ll res = 0;
        for (int i = 1; i <= n; i++)
            res = max(res, (ll)h[i] * (r[i] - l[i] - 1));
        printf("%lld\n", res);
    }
    return 0;
}

• For vector, a dynamic array that can store any type of objects and access them by index, we can use methods like push_back(), pop_back(), insert(), erase(), clear(), size(), empty() and swap() to manipulate the elements. For example:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> nums; // create an empty vector
    for(int i = 0; i < 5; i++)
    {
        nums.push_back(i); // add elements at the end
    }
    cout << "Size: " << nums.size() << endl; // get the number of elements
    cout << "Capacity: " << nums.capacity() << endl; // get the allocated space
    cout << "Front: " << nums.front() << endl; // get the first element
    cout << "Back: " << nums.back() << endl; // get the last element
    cout << "Element at index 2: " << nums[2] << endl; // get the element by index

    nums.insert(nums.begin() + 1, 10); // insert an element at a specific position
    cout << "After insertion: ";
    for(int num : nums) // use range-based for loop to iterate over elements
    {
        cout << num << " ";
    }
    cout << endl;

    nums.erase(nums.begin() + 3); // erase an element at a specific position
    cout << "After erasure: ";
    for(int num : nums)
    {
        cout << num << " ";
    }
    cout<<endl;

   return 0;
}

• For map, an associative container that stores key-value pairs in a sorted order based on their keys, we can use methods like insert(), erase(), find(), count(), clear() and swap() to manipulate the elements. We can also use operator[] or at() to access or modify the value associated with a key. For example:

#include <iostream>
#include <map>
using namespace std;

int main()
{
   map<string, int> scores; // create an empty map
   scores["Alice"] = 90; // insert a key-value pair using operator[]
   scores["Bob"] = 80;
   scores["Charlie"] = 85;
   scores.insert(make_pair("David", 95)); // insert a key-value pair using insert()

   cout<<"Size: "<<scores.size()<<endl; // get the number of elements

   if(scores.find("Bob") != scores.end()) // check if a key exists using find()
   {
       cout<<"Bob's score: "<<scores["Bob"]<<endl;
       scores.erase("Bob"); // erase an element by key using erase()
       cout<<"After erasing Bob"<<endl;
   }

   if(scores.count("Eve") == 0) // check if a key exists using count()
   {
       scores.at("Eve") = 100; // modify or create a value associated with a key using at()
       cout<<"After adding Eve"<<endl;
   }

   for(auto it = scores.begin(); it != scores.end(); it++) 
      /* use iterator to iterate over elements 
      (note that they are sorted by keys in ascending order) */

      /* alternatively, we can also use range-based for loop as follows:
      for(auto p : scores) 
      */

      /* p is a pair object that contains first (key) and second (value) fields */

      /* alternatively, we can also use structured binding as follows:
      for(auto [name,score] : scores)
      */

     { 
         string name = it->first;
         int score = it->second;
         /* alternatively, we can also use tie as follows:
         tie(name,score) = *it;
         */

         /* print out each pair */

         /* alternatively, we can also use structured binding as follows:
         auto [name,score] = *it;
         */

         cout<<name<<": "<<score<<endl;
     }

     return 0;
}

• Set is an associative container that stores unique keys in a sorted order based on their values. Set does not allow two elements to have the same value. Set does not support modifying the value of an element directly because it may break the order of the elements. Set uses a red-black tree as its underlying data structure. Set provides methods such as insert(), erase(), find(), count(), clear() and swap() to manipulate the elements. Set also provides iterators to access and traverse the elements. Set can be constructed with different comparison functions to change its sorting rule.

#include <iostream>
#include <set>
using namespace std;

int main()
{
   set<int> nums; // create an empty set
   nums.insert(10); // insert an element using insert()
   nums.insert(20);
   nums.insert(30);

   cout<<"Size: "<<nums.size()<<endl; // get the number of elements

   if(nums.find(20) != nums.end()) // check if an element exists using find()
   {
       cout<<"Found 20"<<endl;
       nums.erase(20); // erase an element by value using erase()
       cout<<"After erasing 20"<<endl;
   }

   if(nums.count(40) == 0) // check if an element exists using count()
   {
       nums.insert(40); // insert another element
       cout<<"After inserting 40"<<endl;
   }

   for(auto it = nums.begin(); it != nums.end(); it++) 
      /* use iterator to iterate over elements 
      (note that they are sorted by values in ascending order) */

      /* alternatively, we can also use range-based for loop as follows:
      for(int num : nums)
      */

     { 
         int num = *it;         
         /* print out each element */

         cout<<num<<endl;
     }

     return 0;

}

• For unordered_map, an associative container that stores key-value pairs in an unsorted order based on their keys, we can use methods like insert(), erase(), find(), count(), clear() and swap() to manipulate the elements. We can also use operator[] or at() to access or modify the value associated with a key. For example:

#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
    unordered_map<string, int> scores; // create an empty unordered_map
    scores["Alice"] = 90; // insert a key-value pair using operator[]
    scores["Bob"] = 80;
    scores["Charlie"] = 85;
    scores.insert(make_pair("David", 95)); // insert a key-value pair using insert()

    cout<<"Size: "<<scores.size()<<endl; // get the number of elements

    if(scores.find("Bob") != scores.end()) // check if a key exists using find()
    {
        cout<<"Bob's score: "<<scores["Bob"]<<endl;
        scores.erase("Bob"); // erase an element by key using erase()
        cout<<"After erasing Bob"<<endl;
    }

    if(scores.count("Eve") == 0) // check if a key exists using count()
    {
        scores.at("Eve") = 100; // modify or create a value associated with a key using at()
        cout<<"After adding Eve"<<endl;
    }

   for(auto it = scores.begin(); it != scores.end(); it++) 
      /* use iterator to iterate over elements 
      (note that they are not sorted by keys) */

      /* alternatively, we can also use range-based for loop as follows:
      for(auto p : scores) 
      */

      /* p is a pair object that contains first (key) and second (value) fields */

      /* alternatively, we can also use structured binding as follows:
      for(auto [name,score] : scores)
      */

     { 
         string name = it->first;
         int score = it->second;
         /* alternatively, we can also use tie as follows:
         tie(name,score) = *it;
         */

         /* print out each pair */

         /* alternatively, we can also use structured binding as follows:
         auto [name,score] = *it;
         */

         cout<<name<<": "<<score<<endl;
     }

     return 0;
}

• For unordered_set, an associative container that stores unique keys in an unsorted order based on their values, we can use methods like insert(), erase(), find(), count(), clear() and swap() to manipulate the elements. We cannot access or modify individual elements directly because they are immutable. For example:

#include <iostream>
#include <unordered_set>
using namespace std;

int main()
{
   unordered_set<int> nums; // create an empty unordered_set
   nums.insert(10); // insert an element using insert()
   nums.insert(20);
   nums.insert(30);

   cout<<"Size: "<<nums.size()<<endl; // get the number of elements

   if(nums.find(20) != nums.end()) // check if an element exists using find()
   {
       cout<<"Found 20"<<endl;
       nums.erase(20); // erase an element by value using erase()
       cout<<"After erasing 20"<<endl;
   }

   if(nums.count(40) == 0) // check if an element exists using count()
   {
       nums.insert(40); // insert another element
       cout<<"After inserting 40"<<endl;
   }

   for(auto it = nums.begin(); it != nums.end(); it++) 
      /* use iterator to iterate over elements 
      (note that they are not sorted by values) */

      /* alternatively, we can also use range-based for loop as follows:
      for(int num : nums)
      */

     { 
         int num = *it;         
         /* print out each element */

         cout<<num<<endl;
     }

     return 0;

}

#include <bits/stdc++.h>
using namespace std;

const int N = 40;

int n;
int postorder[N], inorder[N]; // 后序，中序遍历
unordered_map<int, int> l, r, pos; // 哈希表模拟二叉树

int build(int il, int ir, int pl, int pr)//中序首尾结点，后序首尾结点
{
    int root = postorder[pr];
    int k = pos[root];

    if(il < k)
        l[root] = build(il, k - 1, pl, pl + (k - 1 - il));
    if(ir > k)
        r[root] = build(k + 1, ir, pl + k - il, pr - 1);

    return root;
}

void bfs(int root)
{
    queue<int> q;
    q.push(root);
    while(q.size())
    {
        auto t = q.front();
        q.pop();

        cout << t << ' ';
        if(l.count(t)) q.push(l[t]);
        if(r.count(t)) q.push(r[t]);
    }

}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++ ) cin >> postorder[i];
    for(int i = 0; i < n; i ++ )
    {
        cin >> inorder[i];
        pos[inorder[i]] = i;  //当通过后续确定root后，通过节点编号找到root在中序中的位置，从而确定左右子树
    }
    int root = build (0, n- 1, 0, n - 1);
    bfs(root);

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second

typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
int n, d, k;
pii logs[N];
int cnt[N];
bool st[N];
int main()
{
    cin >> n >> d >> k;
    for(int i = 0; i < n; i ++ )
    {
        cin >> logs[i].x >> logs[i].y;
    }    

    sort(logs, logs + n);

    for(int i = 0, j = 0; i < n; i ++ )
    {
        int t = logs[i].y;
        cnt[t] ++ ;

        while(logs[i].x - logs[j].x >= d) // 时间窗口不后退
        {
            cnt[logs[j].y] -- ;
            j ++ ;
        }
        if(cnt[t] >= k)
            st[t] = true;
    }

    for(int i = 0; i < N; i ++ )
    {
        if(st[i])
        cout << i << endl;
    }
    return 0;
}

哈希表是一种数据结构，它可以快速地存储和查找键值对。哈希表的核心思想是通过一个哈希函数，将键映射到一个数组的某个位置，然后在该位置存储或查找对应的值。哈希表的优点是查找的时间复杂度是O(1)，缺点是可能会发生哈希冲突，即不同的键被映射到同一个位置，需要额外的方法来解决。

在C++中，可以使用STL中提供的unordered_map来实现哈希表。unordered_map是一个模板类，它接受两个类型参数，分别表示键和值的类型。例如：

// 创建一个以int为键，以string为值的哈希表
unordered_map<int, string> umap;

unordered_map提供了一些常用的成员函数和操作符来操作哈希表，例如：

• umap[key] = value; 通过下标运算符插入或修改一个键值对。
• umap.insert({key, value}); 通过insert函数插入一个键值对。
• umap.erase(key); 通过erase函数删除一个键值对。
• umap.find(key); 通过find函数查找一个键是否存在，返回一个迭代器指向该位置或者end()表示不存在。
• umap.count(key); 通过count函数统计一个键出现的次数，返回0或1。
• umap.size(); 通过size函数返回哈希表中元素的个数。
• umap.empty(); 通过empty函数判断哈希表是否为空。
• umap.clear(); 通过clear函数清空哈希表中所有元素。

贪心，先到先匹配

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll a[N], b[N];
int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ) cin >> a[i];
    for(int i = 0; i < m; i ++ ) cin >> b[i];

    for(int i = 0, j = 0; i < n ; i ++ )//遍历子序列
    {
        while( j < m && a[i] != b[j] ) j ++ ;
        if(j < m && a[i] == b[j])
        {
            j ++ ;
        }
        else if( j == m )
        {
            cout << "No";
            return 0;
        }
    }

    cout << "Yes";
    return 0;
}