LeetCode周赛2021年5月9日_leetcode周赛几分钟完成的都是什么人

太久不写代码了
第一次有空 做LeetCode周赛 不是 下标越界 就是 暴力超时

或者是 明明很简单的题目 就是懒得写 比较麻烦 就不动手

看别人的分享 学习一下

第一题 活着的人 最多的年份

class Solution {
public:
    int yr[3000];
    int maximumPopulation(vector<vector<int>>& logs) {
        for (vector<int> log : logs) {
            int b = log[0];
            int d = log[1];
            for (int i = b; i < d; ++i) ++yr[i];
        }
        int ans = 1950;
        int m = 0;
        for (int i = 1950; i <= 2050; ++i) {
            if (yr[i] > m) {
                m = yr[i];
                ans = i;
            }
        }
        return ans;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第二题就是双指针

class Solution {
public:
    int yr[3000];
    int maximumPopulation(vector<vector<int>>& logs) {
        for (vector<int> log : logs) {
            int b = log[0];
            int d = log[1];
            for (int i = b; i < d; ++i) ++yr[i];
        }
        int ans = 1950;
        int m = 0;
        for (int i = 1950; i <= 2050; ++i) {
            if (yr[i] > m) {
                m = yr[i];
                ans = i;
            }
        }
        return ans;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第三题 空间换时间存储中间值 动态规划

class Solution {
public:
    int a[200001], stk[200001];
    int l[200001], r[200001];
    long long s[200001];
    int maxSumMinProduct(vector<int>& nums) {
        int n = (int )nums.size();
        for (int i = 0; i < n; i ++) {
            a[i + 1] = nums[i];
        }
        for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];
        stk[0] = 0;
        int top = 0;
        long long ans = 0;
        for (int i = 1; i <= n; i ++) {
            while (top && a[stk[top]] >= a[i]) -- top;
            l[i] = stk[top] + 1;
            stk[++ top] = i;
        }
        top = 0; stk[0] = n + 1;
        for (int i = n; i >= 1; i --) {
            while (top && a[stk[top]] >= a[i]) -- top;
            r[i] = stk[top] - 1;
            ans = max(ans, 1LL * a[i] * (s[r[i]] - s[l[i] - 1]));
            stk[++ top] = i;
        }
        return ans % ((int )1e9 + 7);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

子数组最小乘积的最大值