数组与贪心

406. 根据身高重建队列

「代码随想录」带你学透贪心算法！406.根据身高重建队列
image.png

  • vector插入，时间复杂度O(nlogn + n^2)，空间复杂度O(n)

    1. class Solution {
    2. public:
    3.   //排序：一维降序，二维升序
    4.   static bool cmp(vector<int> a, vector<int> b){
    5.       if(a[0] == b[0]) return a[1] < b[1];
    6.       return a[0] > b[0];
    7.   };
    8.   vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    9.       sort(people.begin(), people.end(), cmp);
    11.       vector<vector<int>> res;
    12.       for(int i = 0; i < people.size(); i ++)
    13.       {
    14.           res.insert(res.begin() + people[i][1], people[i]);
    15.       }
    17.       return res;
    18.   }
    19. };

  • list插入，时间复杂度O(nlogn + n^2)，空间复杂度O(n)，避免vector两倍扩容的问题

    class Solution {
public:
  //排序：一维降序，二维升序
  static bool cmp(vector<int> a, vector<int> b){
      if(a[0] == b[0]) return a[1] < b[1];
      return a[0] > b[0];
  };
  vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
      sort(people.begin(), people.end(), cmp);

      list<vector<int>> res;
      for(int i = 0; i < people.size(); i ++)
      {
          list<vector<int>>::iterator it = res.begin();
          int pos = people[i][1];
          while(pos --) it ++;
          res.insert(it, people[i]);
      }

      return vector<vector<int>>(res.begin(), res.end());
  }
};

  • 二分 + 树状数组 O(n∗logn∗logn)

〔manim | 算法 | 数据结构〕 完全理解并深入应用树状数组 | 支持多种动态维护区间操作

  1. 排序 h升序，k降序
  2. 对(h,k)从前往后找到第一个空位，使得当前空位前面有k个空位

二分+树状数组 O（logn∗logn）

class Solution {
public:
    int n;
    vector<int> tr;//树状数组

    int lowbit(int x)//返回最低位1所代表的数值
    {
        return x & -x;
    }

    void add(int x, int k)//给普通数组a[x]加上k,并维护树状数组
    {
        for(int i = x; i <= n; i += lowbit(i))
            tr[i] += k;
    }

    int query(int x)//数组a[x]到x的前缀和
    {
        int res = 0;
        for(int i = x; i; i -= lowbit(i))
            res += tr[i];
        return res;
    }

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        n = people.size();
        tr.resize(n + 1);//树状数组下标从1开始
        vector<vector<int>> res(n);
        sort(people.begin(), people.end(), [](vector<int> a, vector<int> b){
            if(a[0] ==b[0]) return a[1] > b[1];
            return a[0] < b[0];
        });

        for(auto p : people)
        {
            int h = p[0], k = p[1];
            int l = 1, r = n;
            while(l < r)
            {
                int mid = l + r >> 1;
                //数组a[x]表示当前位是否为空，默认为0,如果插入了元素则为1
                //判断第mid位是不是第k+1个空位，空位数=mid-非0位个数，非0位个数=1的个数=前缀和
                if(mid - query(mid) >= k + 1) r = mid;
                else l = mid + 1;
            }
            res[r - 1] = p;//插入，树状数组下标从1开始，输出队列下标从0开始
            add(r, 1);//将a[r]置为1，并维护树状数组
        }

        return res;
    }
};

树状数组：
image.png
image.png
image.png
image.png
image.png
单点修改
image.png
求前缀和
image.png

单调栈

42. 接雨水

  1. 单调栈

image.png

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> stk;//栈存横坐标
        int res = 0;
        for(int i = 0; i < height.size(); i ++)
        {
            int last = 0;//height[上一个栈顶元素],可以任意初始化，因为若i与stk.top()相邻，矩形的宽度为0，面积也为0，不需管高度是多少

            while(stk.size() && (height[stk.top()] <= height[i]))
            {
                res += (i - stk.top() - 1) * (height[stk.top()] - last);
                last = height[stk.top()];
                stk.pop();
            }

            if(stk.size()) res += (i - stk.top() - 1) * (height[i] - last);

            stk.push(i);
        }

        return res;
    }
};
  1. 双指针

接雨水双指针
image.png